Q = int(input())
NK = [list(map(int, input().split())) for _ in range(Q)]
for N, K in NK:
    if K==1:
        print(N-1)
    else:
        i = 0
        N-=K**i
        while N>0:
            i+=1
            N-=K**i
        print(i)