l = list(map(int, input().split()))

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