Q=int(input())

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