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