/*
 *Copyright (c) Swadheen Islam Robi (SIR01)
 *Created on Tue Jan 06 2026 9:12:55 PM
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pie 2 * (acos(0.0))
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define pb push_back
#define endl "\n"
#define lcm(a, b) (a * b) / (__gcd<ll>(a, b))
#define mod 1000000007
#define srt(v) sort(v.begin(), v.end())
#define rsrt(v) sort(v.rbegin(), v.rend())
#define print(vec)        \
    for (auto e : vec)    \
        cout << e << " "; \
    cout << endl
#define ALLAHU_AKBAR             \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);

const ll mx = 32000;
vector<ll> primes;

void sieve()
{
    vector<bool> prime(mx, true);
    prime[0] = prime[1] = false;
    for (ll i = 2; i * i < mx; i++)
    {
        if (prime[i])
        {
            for (ll j = i * i; j < mx; j += i)
                prime[j] = false;
        }
    }
    for (ll i = 2; i < mx; i++)
    {
        if (prime[i])
            primes.pb(i);
    }
}

void sir()
{
    ll x, k;
    cin >> x >> k;

    vector<ll> pf;
    ll temp = x;

    for (ll p : primes)
    {
        if (p * p > temp)
            break;
        while (temp % p == 0)
        {
            pf.pb(p);
            temp /= p;
        }
    }
    if (temp > 1)
        pf.pb(temp);

    srt(pf);
    ll spd = pf[0];

    while (k > 0)
    {
        if (pf.back() == spd)
        {
            if (k % 2 != 0)
            {
                x *= spd; // roy
            }
            break;
        }

        x *= spd;

        pf.insert(pf.begin(), spd);
        k--;

        if (k == 0)
            break;

        ll lpd = pf.back();
        x /= lpd;
        pf.pop_back();
        k--;
    }

    cout << x << endl;
}

int main()
{
    ALLAHU_AKBAR
    sieve();
    ll t;
    cin >> t;
    while (t--)
        sir();
    return 0;
}