Q=int(input())

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