Q = int(input())

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