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