def getPrimeFactorization(n):
    fac = []
    
    for i in range(2, n + 1):
        exp = 0
        while n % i == 0:
            exp += 1
            n //= i
        if exp > 0:
            fac.append([i, exp])
        if n == 1:
            break

    return fac

def numFromFactorization(fac):
    res = 1
    for p, exp in fac:
        if exp == 0:
            break
        res *= p**exp

    return res

def game(x, k):
    fac = getPrimeFactorization(x)
    # print(x)
    # print(fac)
    royMoves = (k + 1) // 2
    hridoyMoves = k - royMoves
    # print(royMoves, hridoyMoves)
    fac[0][1] += royMoves
    for i in range(len(fac) - 1, -1, -1):
        if fac[i][1] < hridoyMoves:
            hridoyMoves -= fac[i][1]
            fac[i][1] = 0
            continue
        fac[i][1] -= hridoyMoves
        break
    return numFromFactorization(fac)

t = int(input())
for _ in range(t):
    x, k = [int(c) for c in input().split(' ')]
    print(game(x, k))