from math import isqrt


is_simple = [True] * (isqrt(10**9) + 1)
is_simple[0] = is_simple[1] = False
is_simple[4::2] = [False] * len(is_simple[4::2])

for i in range(3, isqrt(isqrt(10**9)) + 1, 2):
    if is_simple[i]:
        is_simple[i*i::i] = [False] * len(is_simple[i*i::i])

simple_numbers = []

for i in range(2, isqrt(10**9) + 1):
    if is_simple[i]:
        simple_numbers.append(i)


def get_divisors(x):
    divisors = []
    r = x
    while r != 1:
        for simple_number in simple_numbers:
            if not r % simple_number:
                divisors.append(simple_number)
                r //= simple_number
                break
        else:
            divisors.append(r)
            r = 1
    return divisors


for _ in range(int(input())):
    X, K = map(int, input().split())
    divisors_X = get_divisors(X)
    ans = divisors_X[0]
    if K < 2 * (len(divisors_X) - 1) + 1:
        for divisor in divisors_X[1:len(divisors_X) - K // 2]:
            ans *= divisor
    ans *= divisors_X[0] ** (min(K // 2, len(divisors_X) - 1) + K % 2)
    print(ans)