//* Bismillahir Rahmanir Raheem
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef priority_queue<int> PQ;
typedef priority_queue<int, vector<int> , greater<int>> GPQ;
#define bismillah ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define forcin(n) for(auto &x : n) cin >> x
#define forcout(n) for(auto x : n) cout << x << " "
#define sz(n) (int)n.size()
#define YES cout<< "YES\n"
#define NO cout<< "NO\n"
#define RY {cout<< "YES\n";return;}
#define RN {cout<< "NO\n";return;}
#define F first
#define S second
#define el "\n"
#define sp " "
#define mem(a,b) memset(a,b,sizeof(a)) //shudu 0 & -1
#define gcd(a,b) __gcd(a,b)
#define lcm(x, y) x *(y / gcd(x, y))
#define set_pre(a) cout.unsetf(ios::floatfield); cout.precision(a); cout.setf(ios::fixed,ios::floatfield);
#define preci(x) fixed << setprecision(x)
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define count_bits(x) __builtin_popcountll(x)
#define clz(x) __builtin_clzll(x)
#define ctz(x) __builtin_ctzll(x)
// ======================================================================
// -------------------------- Debugger --------------------------------
template <typename F, typename S> ostream& operator<<(ostream& os, const pair<F, S>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { os << "{"; for (auto it = v.begin(); it != v.end(); ++it) { if (it != v.begin()) os << ", "; os << *it; } return os << "}"; }
template <typename T> ostream& operator<<(ostream& os, const set<T>& v) { os << "["; for (auto it = v.begin(); it != v.end(); ++it) { if (it != v.begin()) os << ", "; os << *it; } return os << "]"; }
template <typename T> ostream& operator<<(ostream& os, const multiset<T>& v) { os << "["; for (auto it = v.begin(); it != v.end(); ++it) { if (it != v.begin()) os << ", "; os << *it; } return os << "]"; }
template <typename F, typename S> ostream& operator<<(ostream& os, const map<F, S>& v) { os << "["; for (auto it = v.begin(); it != v.end(); ++it) { if (it != v.begin()) os << ", "; os << it->first << " = " << it->second; } return os << "]"; }
template <typename T> ostream& operator<<(ostream& os, priority_queue<T> pq) { os << "["; bool first = true; while (!pq.empty()) { if (!first) os << ", "; os << pq.top(); pq.pop(); first = false; } return os << "]"; }
template <typename T> ostream& operator<<(ostream& os, const deque<T>& dq) { os << "["; for (auto it = dq.begin(); it != dq.end(); ++it) { if (it != dq.begin()) os << ", "; os << *it; } return os << "]"; }
template <typename T> ostream& operator<<(ostream& os, queue<T> q) { os << "["; bool first = true; while (!q.empty()) { if (!first) os << ", "; os << q.front(); q.pop(); first = false; } return os << "]"; }
#define dbg(args...) do { cerr << #args << " : "; faltu(args); } while(0)
clock_t tStart = clock();
#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
void faltu() { cerr << endl; }
template <typename T> void faltu(T a[], int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
template <typename T, typename... Args> void faltu(T arg, const Args&... rest) { cerr << arg << ' '; faltu(rest...); }
// -------------------------- END --------------------------------
// ======================================================================

ll bin_exp(ll a, ll n) //O(log(n))
{
  ll r = 1LL;
  while (n) {
    if (n & 1) r = (r * a), n--;
    else a = (a * a), n>>=1ll;
  }
  return r;
}

int mod2 = 1e9 + 7;
inline ll MOD(ll a){ return (a % mod2 + mod2) % mod2; }
inline ll modAdd(ll a, ll b) { return MOD(MOD(a) + MOD(b)); }
inline ll modSub(ll a, ll b) { return MOD(MOD(a) - MOD(b)); }
inline ll modMul(ll a, ll b) { return MOD(MOD(a) * MOD(b)); }
inline ll modInv(ll a) { return bin_exp(a, mod2 - 2); } // buji na


const int M = 1000009;
bool marked[M];
vl primes;
bool isprime(int n) {
  if (n == 2)
    return true;
  if (n < 2 || n % 2 == 0)
    return false;
  return marked[n] == false;
}

void sieve(ll n) {
  for (ll i = 3; i * i <= n; i += 2) {
    if (marked[i] == false) // i is a prime
    {
      for (ll j = i * i; j <= n; j += i) {
        marked[j] = true;
      }
    }
  }
    for (int i = 2; i <= n; i++) {
        if (isprime(i)) {
            primes.pb(i);
            // vector<ll> primes e store korte hobe ei kane
            // age main er initialize korte hobe
        }
    }
}

void solve(){
    ll n,k; cin >> n >> k;
    map<ll,ll> mp;

    for(int i=0; primes[i]*primes[i]<=n; i++){
        while(n%primes[i]==0){
            mp[primes[i]]++;
            n/=primes[i];
        }
    }
    if(n>1)mp[n]++;
    ll x=(k+1)/2, y=k-x;
    ll p=(*mp.begin()).F;
    mp[p]+=x;
    while(!mp.empty() && y>0){
        ll z=min(y,(*mp.rbegin()).S);
        y-=z;
        ll w=(*mp.rbegin()).F;
        mp[w]-=z;
        if(mp[w]==0)mp.erase(w);
    }
    ll ans=1;
    for(auto u:mp){
        ans*=(bin_exp(u.F, u.S));
    }
    cout << ans << el;
}
int main(){
    sieve(1e6);
    bismillah
    int t=1 , tc = 1;
    cin >> t;          
    while(t--){
    //  cout << "Case " << tc++ << ": ";  //! for case
        solve();
    }
    return 0; 
}