Q = int(input())
for _ in range(Q):
    N, K = map(int, input().split())
    N -= 1
    result = 0
    t = K
    while N > 0:
        N -= t
        result += 1
        t *= K
    print(result)