Q = int(input())

for _ in range(Q):
    N, K = map(int, input().split())
    if K == 1:
        print(N - 1)
    else:
        x = 1
        for i in range(1, N):
            x += K ** i
            if N < x:
                print(i)
                break