from math import sqrt

knownPrimes = []

def getPrimeFactorization(n):
    fac = []

    hasDistinctPrimeFactor = False
    for p in knownPrimes:
        exp = 0
        while n % p == 0:
            exp += 1
            n //= p
        if exp > 0:
            hasDistinctPrimeFactor = True
            fac.append([p, exp])
        if n == 1:
            break
    
    squareRootN = int(sqrt(n))
    MIN = max(2, knownPrimes[-1] if knownPrimes else 0)
    for i in range(2, n + 1):
        if i > squareRootN + 1 and not hasDistinctPrimeFactor:
            break
        exp = 0
        while n % i == 0:
            if not knownPrimes or knownPrimes[-1] != i:
                knownPrimes.append(i)
            exp += 1
            n //= i
        if exp > 0:
            hasDistinctPrimeFactor = True
            fac.append([i, exp])
        if n == 1:
            break
    if n != 1:
        fac.append([n, 1])

    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))