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