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