#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...)
#endif

using ul = uint64_t;
ul modMul(ul a, ul b, const ul mod){
	return __int128(a) * __int128(b) % mod;
}
ul modPow(ul a, ul b, const ul mod) {
	if (b == 0) return 1;
	ul res = modPow(a, b/2, mod); 
  res = modMul(res, res, mod);
	return b&1 ? modMul(res, a, mod) : res;
}

bool prime(ul n) { // not ll!
  if (n < 2 || n % 6 % 4 != 1) return n - 2 < 2;
  ul s = __builtin_ctzll(n - 1), d = n >> s;
  ul A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  for (auto a : A) {
    ul p = modPow(a, d, n), i = s;
    while (p != 1 && p != n-1 && a % n && i--) p = modMul(p, p, n);
    if (p != n - 1 && i != s) return false;
  }
  return true;
}

ul pollard(ul n) { // return some nontrivial factor of n
  auto f = [n](ul x) { return modMul(x, x, n) + 1; };
  ul x = 0, y = 0, t = 30, prd = 2, i = 1, q;
  while (t++ % 40 || gcd(prd, n) == 1) { /// speedup: don't take gcd every it
    if (x == y) x = ++i, y = f(x);
    if ((q = modMul(prd, max(x, y)-min(x, y), n))) prd = q;
    x = f(x), y = f(f(y));
  }
  return gcd(prd, n);
}

void factor_rec(ul n, map<ul, int> &cnt) {
  if (n == 1) return;
  if (prime(n)) { ++cnt[n]; return; }
  ul u = pollard(n);
  factor_rec(u, cnt), factor_rec(n/u, cnt);
}

vector<pair<ul, int>> factor(ul n) {
  map<ul, int> cnt;
  factor_rec(n, cnt);
  return vector<pair<ul, int>>(cnt.begin(), cnt.end());
}

int64_t f(vector<pair<ul, int>>& primes) {
  int64_t ans = 1;
  for (auto& [p, e]: primes) {
    for (int i = 0; i < e; i++) {
      ans *= p;
    }
  }
  return ans;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  
  int Q; cin >> Q;
  while (Q--)[&] {
    int n, x;    cin >> n >> x;
    
    // map<ul, int> primes;  
    // factor_rec(n, primes);
    // dbg(primes);

    auto primes = factor(n);
    // dbg(primes);

    int i = 0, len = primes.size();
    for (int pos = len-1; pos > 0 && x > 0; i++) {
      if (i % 2 == 0) primes[0].second++;
      else {
        primes[pos].second--;
        if (primes[pos].second == 0) pos--;
      }
      x--;
    }

    dbg(primes, x, i);

    // x = 0 ; i = 0 ->> 0
    // x = 0 ; i = 1 -->> 0
    // x = 1 ; i = 0 ->> ++
    // x = 1 ; i = 1 ->> --
    if (x % 2 == 1) {
      if (i % 2 == 0) primes[0].second++;
      else primes[0].second--;
    }
    cout << f(primes) << "\n";
  }();
}