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