#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;
}

// Deterministic Miller-Rabin for 64-bit integers
bool isPrime64(u64 n) {
  if (n < 2) return false;
  for (u64 p: {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
    if (n % p == 0) return n == p;
  }
  u64 d = n - 1, s = 0;
  while ((d & 1) == 0) {
    d >>= 1;
    ++s;
  }
  // bases sufficient for 64-bit determinism
  u64 bases[] = {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL};
  for (u64 a: bases) {
    if (a % n == 0) continue;
    u64 x = pow_mod(a % n, d, n);
    if (x == 1 || x == n - 1) continue;
    bool comp = true;
    for (u64 r = 1; r < s; ++r) {
      x = mul_mod(x, x, n);
      if (x == n - 1) {
        comp = false;
        break;
      }
    }
    if (comp) return false;
  }
  return true;
}

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

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);
  }
}