q = int(input())
for _ in range(q):
    n, k = map(int,input().split())
    if k == 1:
        print(n-1)
        continue
    c = 1
    d = 0
    while c < n:
        d += 1
        c += k**d
    print(d)