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