q = int(input())
for _ in range(q):
    n, k = map(int, input().split())
    if k == 1:
        print(n - 1)
    else:
        for i in range(n):
            if pow(k, i) >= n:
                print(i)
                break