#include <bits/stdc++.h>     //   All praise is due to Allah alone, and peace and blessings be
using namespace std;         //         upon him, after whom there is no other Prophet.

vector<int64_t> spf, pr;
void SPF(const int64_t len) {
    spf.resize(len + 1);
    iota(spf.begin(), spf.end(), 0);
    for (int64_t i = 2; i * i <= len; i++) {
        if (spf[i] == i) {
            for (int64_t j = i * i; j <= len; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}
void prime(const int64_t len) {
    SPF(len);
    pr.push_back(2);
    for (int64_t i = 3; i <= len; i += 2) {
        if (spf[i] == i) pr.push_back(i);
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(false);

    prime(1e5);

    int32_t Case = 1;    cin >> Case;
    for (int T = 1; T <= Case; T++) {

        int64_t n, k; cin >> n >> k;
        vector<int64_t> val;
        for(const int64_t i : pr) {
            if(i * i > n) break;
            while(n % i == 0) {
                val.push_back(i);
                n /= i;
            }
        }
        if(n > 1) val.push_back(n);
        sort(val.begin(), val.end());


        int ok = val.size();

        int cnt = min<int64_t>(20, k);
        for(int i = 1; i <= cnt; i++) {
            if(i & 1) {
                val.push_back(val.front());
            }
            else {
                val.pop_back();
            }
            sort(val.begin(), val.end());
        }
        if(k > 20 and k & 1) {
            val.push_back(val.front());
        }
        int64_t ans = 1;
        
        for(const int64_t i : val) {
            ans *= i;
        }
        cout << ans << '\n';
    }
    return 0;
}