q=int(input())
for _ in range(q):
    n,k=map(int,input().split())
    if k==1:
        print(n-1)
    else:
        for p in range(1,100):
            if k**p>=n:
                print(p)
                break