#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<pair<int, int>> prime_factors(int n)
{
    vector<pair<int, int>> factors;

    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            int cnt = 0;
            while (n % i == 0)
            {
                n /= i;
                cnt++;
            }
            factors.push_back({(int)i, cnt});
        }
    }

    if (n > 1)
        factors.push_back({(int)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);
    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;

        while (true)
        {
            int curr = factors.back().second;
            if (second <= curr)
            {
                factors.back().second -= second;
                if (factors.back().second == 0)
                    factors.pop_back();
                second = 0;
                break;
            }
            else
            {
                second -= factors.back().second;
                factors.pop_back();
            }
        }
        int res = 1;

        for (auto a : factors)
        {
            res = (res * binpow(a.first, a.second));
        }
        cout << res << endl;
    }
    return 0;
}