/*in the name of almighty ALLAH*/

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define endl '\n'
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define MOD 1000000007
#define MOD2 987654319
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define sz(x) (int)x.size()

template <typename T> using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using multi_pbds = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

//***********************************START*******************************************//

const int sz = 1e5 + 5;
vector <bool> marked(sz, true);
vector <int> primes;

void sieve()
{
    int i, j;

    for (i = 3; i * i < sz; i += 2) {
        if (marked[i]) {
            for (j = i * i; j < sz; j += 2 * i) {
                marked[j] = false;
            }
        }
    }

    primes.push_back(2);

    for (i = 3; i < sz; i += 2) {
        if (marked[i]) {
            primes.push_back(i);
        }
    }
}

vector < int > Prime_Factor( int N )
{
    vector < int > factor;
    for(auto P : primes)
    {
        if(1LL * P * P > N) break;
        if(N % P == 0)
        {
            while(N % P == 0)
            {
                factor.push_back(P);
                N /= P;
            }
        }
    }
    if(N > 1) factor.push_back(N);
    return factor;
}

void solve()
{
    int n, k; cin >> n >> k;
    vector < int > a = Prime_Factor(n);

    int hrid = k/2, roy = k - hrid, pw = 0, ans = 1;
    sort(all(a));
    int small = a[0];

    if(hrid >= sz(a)){
        hrid -= sz(a);
        roy -= hrid;
    }
    else{
        pw = sz(a) - hrid;
        for(int i = 0; i < pw; i++){
            ans *= a[i];
        }
    }

    for(int i = 1; i <= roy; i++) ans *= small;
    cout << ans << endl;
}

//***********************************END*********************************************//
int32_t main(){ fast

    int32_t t = 1, i;
    sieve();
      cin >> t;
    for(i = 1; i <= t; i++)
    {
       // cout << "Case " << i << ": ";
        solve();
    }
}