Q = int(input())
for case in range(Q):
    N, K = map(int, input().split())
    if K == 1:
        print(N - 1)
        continue
    node = 1
    depth = 0
    K0 = K
    while node < N:
        node += K
        K *= K0
        depth += 1
    print(depth)