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