#include<numeric>
#include<random>
#include <iostream>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <string>
#include <complex>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<cmath>

#ifdef __GNUC__
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#endif
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using namespace std;
bool c = 1;
inline ll msb(ll x) {
    if (!x)
        return -1;
#ifdef _MSC_VER
    unsigned long ret;
    _BitScanReverse64(&ret, x);
    return ret;
#endif
#ifdef __GNUC__
    int ret = 63 - __builtin_clzll(x);
    return ret;
#endif
    return 0;
}
char b_s(ll k) {
    int b = 0, e = 1e9;
    while (b < e - 1) {
        int m = (b + e) >> 1;
        ll as = m * (m + 1ll) / 2;
        ll bs = m;
        if (as + bs > k)
            e = m;
        else b = m;
    }
    ll v = b * (b + 1ll) / 2 + b;
    if (v == k)
        return 'b';
    else return 'a';
}
void nine11(int tst) {
    map<int, int> fac;
    int n, k; cin >> n >> k;
    for (int i = 2; i <= n; i++) {
        if (1ll * i * i > n)i = n;
        if (n % i)continue;
        while (n % i == 0)n /= i, fac[i]++;
    }
    int t = 0;
    int p = fac.begin()->first;
    int q = fac.rbegin()->first;
    while (k > 0 && p != q) {
        k--;
        if (t == 0) {
            fac[p]++;
        }
        else {
            fac[q]--;
            if (!fac[q]) {
                fac.erase(q);
                q = fac.rbegin()->first;
            }
        }
        t ^= 1;
    }
    if (k % 2) {
        if (t == 0)
            fac[p]++;
        else fac[p]--;
    }
    ll ans = 1;
    for (auto kv : fac) {
        while (kv.second -- ) {
            ans *= kv.first;
        }
    }
    cout << ans << '\n';
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1; cin >> t;
    for (int i = 1; i <= t && c; i++) {
        nine11(i);
    }
    cout.flush();
    return 0;
}