#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// #ifndef ONLINE_JUDGE
// #include "template.cpp"
// #else
// #define debug(...)
// #define debugArr(...)
// #endif

#define F first
#define S second
#define ll long long
#define double long double
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define INF (ll)1e18
#define ordered_set                              \
    tree<pii, null_type, less<pii>, rb_tree_tag, \
         tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using pbb = pair<bool, bool>;
using pcc = pair<char, char>;
using pss = pair<string, string>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<double>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
using vpdd = vector<pair<double, double>>;
using vpbb = vector<pair<bool, bool>>;
using vpcc = vector<pair<char, char>>;
using vpss = vector<pair<string, string>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvd = vector<vector<double>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;
using vvpii = vector<vector<pair<int, int>>>;
using vvpll = vector<vector<pair<ll, ll>>>;
using vvpdd = vector<vector<pair<double, double>>>;
using vvpbb = vector<vector<pair<bool, bool>>>;
using vvpcc = vector<vector<pair<char, char>>>;
using vvpss = vector<vector<pair<string, string>>>;

// clang-format off
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T> T sqrt_(T elem) {int l=1,r=elem;while(l<=r){int mid=l+(r-l)/2LL;if(mid>elem/mid){r=mid-1;}else{int val=mid*mid;if(val<=elem){l=mid+1;}else{r=mid-1;}}}return r;}
template <class T> T ceil_(T a,T b) {return(a+b-1)/b;};
// clang-format on
static constexpr int MOD = 1e9 + 7, MAX_N = 1000010;

struct Mint {
    int x;

    Mint(ll x = 0) : x((x % MOD + MOD) % MOD) {}

    explicit operator int() const { return x; }

    bool operator==(const Mint &rhs) const { return x == rhs.x; }

    bool operator!=(const Mint &rhs) const { return !(rhs == *this); }

    friend Mint operator+(const Mint &l, const Mint &r) {
        return l.x + r.x;
    }

    Mint &operator+=(const Mint &o) { return *this = *this + o; }

    friend Mint operator-(const Mint &l, const Mint &r) {
        return l.x - r.x;
    }

    Mint operator-() const { return -x; }

    Mint &operator-=(const Mint &o) { return *this = *this - o; }

    friend Mint operator*(const Mint &l, const Mint &r) {
        return (ll)l.x * r.x;
    }

    Mint &operator*=(const Mint &o) { return *this = *this * o; }

    Mint pow(ll b) const {
        Mint ans = 1;
        Mint a = *this;
        for (; b; b >>= 1, a = a * a)
            if (b & 1)
                ans *= a;
        return ans;
    }

    friend Mint operator/(const Mint &l, const Mint &r) {
        return l * r.pow(MOD - 2);
    }

    Mint &operator/=(const Mint &o) { return *this = *this / o; }

    friend ostream &operator<<(ostream &os, const Mint &o) {
        return os << o.x;
    }
};

Mint fac[MAX_N] = {1}, rfac[MAX_N] = {1};

void prep() {
    for (int i = 1; i < MAX_N; ++i)
        fac[i] = fac[i - 1] * i;
    rfac[MAX_N - 1] = 1 / fac[MAX_N - 1];
    for (int i = MAX_N - 2; i >= 0; --i)
        rfac[i] = (i + 1) * rfac[i + 1];
}

Mint ncr(int n, int r) {
    return n < r || r < 0 ? 0 : fac[n] * rfac[r] * rfac[n - r];
}

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

    ll tempX = x;
    vpll vals;

    if (tempX % 2 == 0) {
        int cnt = 0;
        while (tempX % 2 == 0) {
            tempX /= 2;
            cnt++;
        }
        vals.eb(2, cnt);
    }

    for (int i = 3; i * i <= x; i += 2) {
        if (tempX % i == 0) {
            int cnt = 0;
            while (tempX % i == 0) {
                tempX /= i;
                cnt++;
            }
            vals.eb(i, cnt);
        }
    }

    if (tempX > 1) {
        vals.eb(tempX, 1);
    }

    int turn = 0, currK = 0;

    for (int i = sz(vals) - 1; i >= 0; i--) {
        for (int j = 1; j <= vals[i].S;) {
            if (turn & 1) {
                x /= vals[i].F;
                j++;
            } else {
                x *= vals[0].F;
            }
            turn++;
            currK++;
            if (currK == k) {
                break;
            }
        }
        if (currK == k) {
            break;
        }
    }

    if (currK == k) {
        cout << x << '\n';
        return;
    }

    int rem = k - currK;

    if (rem & 1) {
        if (turn & 1) {
            x /= vals[0].F;
        } else {
            x *= vals[0].F;
        }
    }

    cout << x << '\n';
    return;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int tt = 1, count = 1;
    cin >> tt;
    while (tt--) {
        // cout << "Case #" << count << ": ";
        solve();
        ++count;
    }
    return 0;
}