#include <iostream>
#include <vector>

using namespace std;

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

    vector<long long> divs;
    long long tmp = n;

    if (tmp % 2 < 1) {
        divs.push_back(2);
        while (tmp % 2 < 1) {
            tmp /= 2;
        }
    }
    if (tmp % 3 < 1) {
        divs.push_back(3);
        while (tmp % 3 < 1) {
            tmp /= 3;
        }
    }

    long long i = 5;
    while (i * i <= tmp) {
        if (tmp % i < 1) {
            divs.push_back(i);
            while (tmp % i < 1) {
                tmp /= i;
            }
        }
        if (tmp % (i + 2) < 1) {
            divs.push_back(i + 2);
            while (tmp % (i + 2) < 1) {
                tmp /= (i + 2);
            }
        }
        i += 6;
    }
    if (tmp > 1) {
        divs.push_back(tmp);
    }

    long long x = 0;
    while (divs.size() > 1 && x < k) {
        if (x % 2 < 1) {
            n *= divs[0];
        } else {
            while (n % divs.back()) {
                divs.pop_back();
            }
            n /= divs.back();
        }
        x++;
    }

    long long rem = k - x;
    if (rem && rem % 2) {
        if (!divs.empty() && n == divs[0]) {
            cout << n * n << "\n";
        } else {
            if (x % 2 < 1) {
                cout << n * divs[0] << "\n";
            } else {
                cout << n / divs[0] << "\n";
            }
        }
    } else {
        cout << n << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}