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