q = int(input())
info = [list(map(int, input().split())) for i in range(q)]

for i in range(q):
    n, k = info[i]
    if k == 1:
        print(n - 1)
        continue
    ans = 0
    while n > 0:
        n -= k**ans
        ans += 1
    print(ans - 1)