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