import math
for _ in range(int(input())):
    N, K = map(int, input().split())
    if K == 1:
        ans = N - 1
    else:
        ans = math.ceil(math.log(N, K))
    print(ans)