#include <bits/stdc++.h>
using namespace std;

#define int long long int 
vector<bool> isPrime;
vector<int> primes;
void init_sieve(int n,bool genArr){
    isPrime.resize(n, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2;  i*i < n; i++){
        if (isPrime[i]){
            for (int j = i*i; j < n; j+=i) isPrime[j] = false;
        }
    }
    if (genArr){
      for (int i=2; i<n;i++) {
        if (isPrime[i]) primes.push_back(i);
      }
    }
}

long long binexp(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    #ifdef SUBLIME
        freopen("inputf.in", "r", stdin);
        freopen("outputf.out", "w", stdout);
        freopen("error.txt", "w", stderr);
    #endif

    init_sieve(1e5, true);

    int tt;
    cin >> tt;

    while (tt--) {
        int n, k;
        cin >> n >> k;

        vector <pair <int, int>> vp;
        for (auto p : primes) {
            if (p * 1LL * p > n) break;
            if (n % p == 0) {
                int cnt = 0;
                while (n % p == 0) {
                    n /= p;
                    cnt++;
                }
                vp.push_back({p, cnt});
            }
        }
        if (n > 1) vp.push_back({n, 1});

        int dcnt = k / 2, mcnt = k - dcnt;

        vp.front().second += mcnt;
        for (int i = vp.size() - 1; i >= 0; i--) {
            int x = min(dcnt, vp[i].second);
            vp[i].second -= x;
            dcnt -= x;
            if (dcnt == 0) break;
        }

        int ans = 1;
        for (auto [v, f] : vp) ans *= binexp(v, f);
        cout << ans << "\n";
    }   
    return 0;
}