Q = int(input())

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