n = int(input())
for i in range(n):
    a, b = map(int,input().split())
    if b == 1:
        print(a - 1)
        continue
    res = 0
    c = 0
    while c < a:
        c += b ** res
        res += 1
    print(res - 1)