Q=int(input())
for i in range(Q):
    N,K=map(int,input().split())
    if K==1:
        print(N-1)
    else:
        cnt=1
        depth=0
        while N>cnt:
            cnt+=K**(depth+1)
            depth+=1
        print(depth)