#include <bits/stdc++.h>
using namespace std;
     
const long long mod = 10000007;
const long long INF = LLONG_MAX;
const int N = 2e6 + 9;

vector<long long> v1;
bitset<N + 5> nprime;

void SieveOfEratosthenes(int n) {
    v1.push_back(2);
    
    for (int p = 3; p * p < n; p += 2) {
        if (!nprime[p]) {
            for (long long i = (long long)p * p; i < n; i += 2 * p) {
                nprime[i] = true;
            }
        }
    }
    for (int p = 3; p < n; p += 2) {
        if (!nprime[p]) {
            v1.push_back(p);
        }
    }
}

void solve () {
    long long n, k;
    vector <long long> v;
    cin >> n >> k;

    long long sum = n;

    for (int i = 0; v1[i] * v1[i] <= sum; i++) {
        while (n % v1[i] == 0) {
            v.push_back (v1[i]);
            n = n / v1[i];
        }
    }
    if (n != 1) {
        v.push_back (n);
    }
    int x = v.size() - 1;

    long long sum1 = sum;

    for (int i = 1; i <= min (k, 100LL); i++) {
        if (i % 2 == 1) {
            sum = sum * v[0];
        } else {
            sum = sum / v[x];
            x--;
        }
        if ((k >= 100 && i >= 100) || (x == -1)) {
            if (k % 2 == 0) {
                cout << sum;
                return;
            } else {
                cout << (sum * v[0]);
                return;
            }
        }
        sum1 = sum;
    }
    cout << sum;
} 
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    SieveOfEratosthenes(1001000);

    long long t;
    cin >> t;

    while (t--) {
        solve();
        cout << "\n";
    }
    return 0;
}