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

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

    long long sum = n;

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

    long long sum1 = sum;

    for (int i = 1; i <= k; i++) {
        if (i % 2 == 1) {
            sum = sum * v[0];
        } else {
            sum = sum / v[x];
            x--;
        }
        if (sum == sum1) {
            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); 

    long long t;
    cin >> t;

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