#include <bits/stdc++.h>
using namespace std;
#define debug(a) cerr << #a << " = " << (a) << nl;
#define ll long long
#define int long long
#define nl '\n'

deque<int> primeFactors(int x)
{
    deque<int> a;
    for (int k = 2; k*1ll*k <= x; ++k)
            while (x % k == 0)
                x /= k, a.push_back(k);
    if (x > 1)
        a.push_back(x);
    return a;
}

void jAVA()
{
    int n, k; cin >> n >> k;
    auto a = primeFactors(n);
    int mv = 1;
    sort(a.begin(), a.end());
    while(k) {
        if(a.front() == a.back() and mv == 1) break;
        if(mv) {
            a.push_front(a[0]);
        }
        else {
            a.pop_back();
        }
        mv ^= 1;
        k--;
    }
    k %= 2;
    if(k) a.push_back(a[0]);
    int ans = 1;
    for(auto i: a) ans *= i;
    cout << ans << nl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int t = 1, cs = 0;
    cin >> t;
    while (t--){
        // cout << "Case " << ++cs << ": ";
        jAVA();
    }
    return 0;
}