#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <cstring>
#include <unordered_map>
#include <iomanip>
#include <queue>
#include <map>
#include <sstream>
#include <stack>
#include <bitset>
#include <random>

using ll = long long;

using namespace std;

constexpr int nm = 32000;

vector<ll> primes;
vector<bool> isPrime(nm, 1);
ll n, k;

vector<pair<ll, ll>> factorize(ll n) {
    vector<pair<ll, ll>> res;
    for (ll i: primes) {
        if (i * i > n) break;
        if (n % i == 0) {
            ll cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            res.emplace_back(i, cnt);
        }
    }
    if (n > 1) res.emplace_back(n, 1);
    return res;
}

void solve() {
    cin >> n >> k;
    auto factors = factorize(n);

    ll i = 0;
    while (i < k && factors.size() > 1) {
        i++;
        if (i % 2) {
            factors.begin()->second++;
        } else {
            auto it = prev(factors.end());
            it->second--;
            if (it->second == 0) factors.pop_back();
        }
    }

    if ((k - i) % 2) {
        i++;
        if (i % 2) {
            factors.begin()->second++;
        } else {
            auto it = prev(factors.end());
            it->second--;
            if (it->second == 0) factors.pop_back();
        }
    }

    ll res = 1;
    for (auto &[x, y]: factors) {
        for (int i = 0; i < y; ++i) res *= x;
    }
    cout << res << "\n";
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (ll i = 2; i < nm; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (ll j = i * i; j < nm; j += i) isPrime[j] = 0;
        }
    }

    int t;
    cin >> t;
    while (t--) solve();
}