Q=int(input())

for _ in range(Q):
    N,K=map(int,input().split())
    if K==1:
        print(N-1)
        continue
    temp=1
    count=0
    while N>0:
        N-=temp
        count+=1
        temp*=K
    print(count-1)