Q, *NK = map(int, open(0).read().split())

for N, K in zip(*[iter(NK)] * 2):
    if K == 1:
        print(N - 1)
    else:
        cnt = 0
        cur = 1
        while cur < N:
            cur *= K
            cnt += 1
        print(cnt)