#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
        OBSERVATIONS:


    x has some smallest factor


    and a lot of other factor..


    the array woudl look something like this:

    2,2,2,2...,3,3,3,3,3...,5,5,5,5,5...,7,7,7..


    roy keeps adding in front

    and hridoy keeps poping from the back..

    although they have said current x ..

    that means it will be the factor only...


    12

    2,3

    2,2,3
    2,3


    adding is constant

    that is (k+1)/2 times ..

    and then i have k/2 operations that i can mostly

    BF .




*/
vector<int> primes;
void sieve()
{
    const int MAXP = 31623;
    vector<bool> is_prime(MAXP + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i <= MAXP; i++)
    {
        if (is_prime[i])
        {
            for (int j = i * i; j <= MAXP; j += i)
                is_prime[j] = false;
        }
    }

    for (int i = 2; i <= MAXP; i++)
        if (is_prime[i])
            primes.push_back(i);
}
vector<pair<int, int>> prime_factors(int n)
{
    vector<pair<int, int>> factors;

    for (int p : primes)
    {
        if (1LL * p * p > n)
            break;

        if (n % p == 0)
        {
            int cnt = 0;
            while (n % p == 0)
            {
                n /= p;
                cnt++;
            }
            factors.push_back({p, cnt});
        }
    }

    if (n > 1)
        factors.push_back({n, 1});

    return factors;
}

int binpow(int a, int b)
{
    int res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve();
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        int first = (k + 1) / 2;
        int second = k / 2;
        vector<pair<int, int>> factors = prime_factors(n);

        factors[0].second += first;

        int size = factors.size() - 1;
        int last_index = size;
        while (last_index >= 0)
        {
            int curr = factors[last_index].second;
            if (second <= curr)

            {

                factors[last_index].second -= second;
                if (factors[last_index].second == 0)
                {
                    last_index--;
                }
                second = 0;
                break;
            }
            else
            {

                second -= factors[last_index].second;
                last_index--;
            }
        }
        int res = 1;

        for (int i = 0; i <= last_index; i++)
        {
            pair<int, int> a = factors[i];

            res = (res * binpow(a.first, a.second));
        }
        cout << res << endl;
    }
    return 0;
}