q=int(input())
for i in range(q):
    n,k=map(int,input().split())
    p=1
    a=0
    if k==1:
        a=n-1
    else:
        while p<n:
            p+=k*k**a
            a+=1
            
    print(a)