q = int(input())

for i in range(q):
    n, k = map(int, input().split())

    if k == 1:
        print(n - 1)
    else:
        i = 0
        while k ** i < n:
            ans = k ** i
            i += 1
        print(i)