q = int(input())
for _ in range(q):
    n,k = map(int, input().split())
    if k == 1: print(n-1); continue
    t = g = 0
    while g < n:
        g += k**t
        t += 1
    print(t-1)