import math

Q = int(input())

for _ in range(Q):
    N, K = map(int, input().split())
    if K == 1:
        print(N - 1)
    else:
        print(math.ceil(N ** (1/K)))