q = int(input())
for _ in range(q):
    n,k = map(int,input().split())
    if k==1:
        print(n-1)
        continue
    d = 1
    node = 1
    while True:
        node *= k
        d += 1
        if node >= n:
            break
    print(d-1)