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