#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key

#define endl           "\n"
#define F              first
#define S              second
#define pb             push_back
#define mp             make_pair
#define ub             upper_bound
#define lb             lower_bound
#define int            long long int
#define pii            pair <int, int>
#define vi             vector <int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define si             set <int>
#define spi            set <pii>
#define double         long double
#define cy             cout<<"YES"<<endl;
#define cn             cout<<"NO"<<endl;
#define sz(x)          ((int) x.size())
#define all(v)         v.begin(), v.end()
#define srt(v)         sort(v.begin(),v.end());
#define rsrt(v)        sort(v.rbegin(),v.rend());
#define mnv(v)         *min_element(v.begin(),v.end())
#define mxv(v)         *max_element(v.begin(),v.end())
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define print1(a)      for(auto x : a) cout << x << " "; cout << endl;
#define print2(a)      for(auto x : a) cout << x.F << " " << x.S << endl;
#define print3(a,s,e)  for(int i=s; i<=e; i++) cout<< a[i] <<" "; cout << endl;
#define vin(x,n)       vi x(n); for (int i = 0; i < n; ++i){ cin>>x[i]; }
#define srtbypairsc(v) sort(v.begin(), v.end(), []( pair<int, int>& l, pair<int, int>& r) { return l.second < r.second; } );

void __print(int x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) { cerr << (f++ ? "," : ""), __print(i); } cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) { cerr << ", "; } _print(v...);}
#ifndef ONLINE_JUDGE
#define bug(x...) cerr << "[" << #x << "] = ["; _print(x);
#else
#define bug(x...);
#endif

const int MOD = 1e9 + 7;
const int N = 200005;
const int M = 5000005;

vector<bool> isprime(M, true);
vi primes;
int SPF[M];

void genprimes() {
    isprime[0] = isprime[1] = false;
    for (int i = 0; i < M; i++) { SPF[i] = i; }
    for (int i = 2; i < M; i++) {
        if (isprime[i]) {
            primes.pb(i); SPF[i] = i;
            for (long long j = 1LL * i * i; j < M; j += i) { isprime[j] = false; if (SPF[j] == j) { SPF[j] = i; }}
        }
    }
}
int MEX(vector<int> &a) {
    vector<bool> f(a.size() + 1, 0);
    for (int i : a) if (i <= (int) a.size()) { f[i] = 1; }
    int mex = 0;
    while (f[mex]) { ++mex; } return mex;
}
int ceil_div(int a, int b) { return a / b + ((a ^ b) > 0 && a % b != 0);}
int gcd(int a, int b) { a = abs(a), b = abs(b);  return b ? gcd(b, a % b) : a;}
int lcm(int a, int b) { a = abs(a), b = abs(b);  return a / gcd(a, b) * b;  }
int add(int a, int b) {return ((a % MOD) + (b % MOD)) % MOD;}
int multi(int a, int b) { return ((a % MOD) * (b % MOD)) % MOD;}
int expo(int a, int b) { if (!b) { return 1; } int e = expo(a, b / 2); if (b % 2) { return multi(a, multi(e, e)); } else { return multi(e, e); }}
int INV(int a) { return expo(a, MOD - 2);}
int divide(int a, int b) {return multi(a, INV(b));}
int fact[M];
void genfact() {fact[0] = 1; for (int i = 1; i < M; i++) { fact[i] = (fact[i - 1] * i) % MOD; } }
int NCR(int n , int r) {
    if (n < r) { return 0; }
    return (((fact[n] * INV(fact[n - r])) % MOD) * INV(fact[r]) % MOD) % MOD;
}
/*-------------------------------------------------------------------------------------------------------------------------------------*/


void solve() {

    int x, k;
    cin >> x >> k;

    int y = x;

    mii m;

    for (int i = 2; i * i <= y; ++i) {
        int z = 0;

        while (y % i == 0) {
            y /= i;
            z++;
        }

        if (z) {
            m[i] = z;
        }
    }

    if (y > 1) {
        m[y] = 1;
    }



    if (sz(m) == 1 && m.begin()->S == 1 && m.begin()->F == x) {
        if (k & 1) {
            cout << x *x << endl;
        }
        else {
            cout << x << endl;
        }

        return;
    }



    bug(m)

    int p = k / 2;

    while (p > 0 && sz(m) >= 2) {


        int a = m.begin()->F;
        int aa = m[a];
        int b = m.rbegin()->F;
        int bb = m[b];

        int mi = min(p, b);

        x = (x * expo(a, mi)) / expo(b, mi);

        m[a] += mi;
        p -= mi;

        if (bb = mi) {
            m.erase(m.rbegin()->F);
        }
        else {
            m[a] -= mi;
        }


    }

    if (k & 1) {
        x *= m.begin()->F ;
    }

    cout << x << endl;


}
//cout<<fixed<<setprecision(6);

int32_t main() {

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);



    clock_t z = clock();
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout<<"Case "<<i<<": ";
        solve();
    }
    cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);
    return 0;
}