for _ in range(int(input())):
    n,k=map(int,input().split())
    if k==1:
        print(n-1)
        break
    ans=0;cur=1;sm=1
    while sm<n:
        cur*=k
        sm+=cur
        ans+=1
    print(ans)