for _ in range(int(input())):
    n,k=map(int,input().split())
    if k==1:
        print(n-1)
    else:
        cnt,ans=1,0
        while n>cnt:
            cnt*=k
            ans+=1
        print(ans)