#include <bits/stdc++.h>

using namespace std;

/*#define int int64_t*/
#define el '\n'

using u128 = __uint128_t;
using u64 = uint64_t;

u64 mul_mod(u64 a, u64 b, u64 mod) {
  return (u128) a * b % mod;
}

u64 pow_mod(u64 a, u64 e, u64 mod) {
  u64 r = 1;
  while (e) {
    if (e & 1) r = mul_mod(r, a, mod);
    a = mul_mod(a, a, mod);
    e >>= 1;
  }
  return r;
}

// Pollard-Rho
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());

bool isPrime64(u64 n, int iterations = 7) {
  if (n < 2) return false;
  // small prime trial division to speed up and avoid degenerate ranges
  for (u64 p: {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
    if (n % p == 0) return n == p;
  }
  // write n-1 as d * 2^s
  u64 d = n - 1;
  int s = 0;
  while ((d & 1) == 0) {
    d >>= 1;
    ++s;
  }
  // if n is small (<= 40) above loop already handled it; otherwise safe to pick bases in [2, n-2]
  uniform_int_distribution<u64> dist(2, n - 2);
  for (int it = 0; it < iterations; ++it) {
    u64 a = dist(rng64);
    u64 x = pow_mod(a, d, n);
    if (x == 1 || x == n - 1) continue;
    bool composite = true;
    for (int r = 1; r < s; ++r) {
      x = mul_mod(x, x, n);
      if (x == n - 1) { composite = false; break; }
    }
    if (composite) return false;
  }
  return true; // probably prime
}

u64 pollard_f(u64 x, u64 c, u64 mod) {
  return (mul_mod(x, x, mod) + c) % mod;
}

u64 rho(u64 n) {
  if (n % 2ULL == 0ULL) return 2ULL;
  if (n % 3ULL == 0ULL) return 3ULL;
  u64 c = uniform_int_distribution<u64>(1, n - 1)(rng64);
  u64 x = uniform_int_distribution<u64>(2, n - 2)(rng64);
  u64 y = x;
  u64 d = 1;
  while (d == 1) {
    x = pollard_f(x, c, n);
    y = pollard_f(pollard_f(y, c, n), c, n);
    u64 diff = x > y ? x - y : y - x;
    d = std::gcd(diff, n);
    if (d == n) return rho(n);
  }
  return d;
}

void factor_rec(u64 n, vector<u64> &out) {
  if (n == 1) return;
  if (isPrime64(n)) {
    out.push_back(n);
    return;
  }
  u64 d = rho(n);
  factor_rec(d, out);
  factor_rec(n / d, out);
}

void run_case(int tc) {
  u64 n, k;
  cin >> n >> k;
  vector<u64> f;
  factor_rec(n, f);
  map<int, int> fq;
  for (int x: f) {
    fq[x] += 1;
  }
  while (fq.size() > 1 && k > 0) {
    fq.begin()->second += 1;
    k -= 1;
    if (k > 0) {
      prev(fq.end())->second -= 1;
      if (prev(fq.end())->second == 0) {
        fq.erase(prev(fq.end()));
      }
      k -= 1;
    }
  }
  u64 x = 1;
  for (auto [p, e]: fq) {
    while (e--) {
      x *= p;
    }
  }
  if (k & 1) {
    x *= fq.begin()->first;
  }
  cout << x << el;
}

int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int _t = 1;
  cin >> _t;
  for (int i = 1; i <= _t; i++) {
    run_case(i);
  }
}