A = int(input())
for i in range(1, len(A)):
    N, K = map(int, input().separate())
    cnt = 0
    j = 0
    while N > 0:
        N -= K ** j
        cnt += 1
        j += 1
    print(cnt-1)