#include <bits/stdc++.h>     //   All praise is due to Allah alone, and peace and blessings be
using namespace std;         //         upon him, after whom there is no other Prophet.

const int mod = 998244353;
int pow_mod(int64_t n, int64_t k) {
    int64_t r = 1; n %= mod;
    while (k) {
        if (k & 1) r = r * n % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return r;
}
int add(int64_t a, int64_t b) {
    a %= mod, b %= mod;
    a += b;
    return (a >= mod) ? a - mod : a;
}
int sub(int64_t a, int64_t b) {
    a %= mod, b %= mod;
    a -= b;
    return (a < 0) ? a + mod : a;
}
int mul(int64_t a, int64_t b) {
    a %= mod, b %= mod;
    return (a * b) % mod;
}
int mdiv(int64_t a, int64_t b) {
    a %= mod, b %= mod;
    return a * pow_mod(b, mod - 2) % mod;
}

int64_t lcm(const int64_t a, const int64_t b) {
    return (a / __gcd(a, b)) * b;
}
int64_t c_dist(const int64_t x1, const int64_t y1, const int64_t x2, const int64_t y2) {
    return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}
int msb(const int64_t x) {
    return x ? 63 - __builtin_clzll(x) : -1;
}
int lsb(const int64_t x) {
    return x ? __builtin_ctzll(x) : -1;
}
bool kthbit(const int64_t x, const int k) {
    return (x >> k) & 1;
}

struct Array { int f, inf; }; vector<Array> Cc;
void combinatorics(const int N) {
    Cc.resize(N);
    Cc[0].f = 1;
    for (int i = 1; i < N; i++) {
        Cc[i].f = int64_t(Cc[i - 1].f) * i % mod;
    }
    Cc[N - 1].inf = pow_mod(Cc[N - 1].f, mod - 2);
    for (int i = N - 2; i >= 0; i--) {
        Cc[i].inf = int64_t(Cc[i + 1].inf) * (i + 1) % mod;
    }
}
int ncr(const int n, const int r) {
    return mul(mul(Cc[n].f, Cc[r].inf), Cc[n - r].inf);
}
int npr(const int n, const int r) {
    return mul(Cc[n].f, Cc[n - r].inf);
}

vector<int> spf, pr;
void SPF(const int len) {
    spf.resize(len + 1);
    iota(spf.begin(), spf.end(), 0);
    for (int i = 2; i * i <= len; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j <= len; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}
void prime(const int len) {
    SPF(len);
    pr.push_back(2);
    for (int i = 3; i <= len; i += 2) {
        if (spf[i] == i) pr.push_back(i);
    }
}
vector<pair<int,int>> pf(int n) {
    vector<pair<int,int>> f;
    while (n > 1) {
        int p = spf[n], cnt = 0;
        while (n % p == 0) {
            n /= p;
            cnt++;
        }
        f.emplace_back(p, cnt);
    }
    return f;
}
bool is_prime(const int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    int64_t d = n - 1;
    while ((d & 1) == 0) d >>= 1;
    int64_t bases[3] = {2, 7, 61};
    for (int64_t a: bases) {
        if (a >= n) continue;
        int64_t t = d, y = 1, b = a % n;
        while (t) {
            if (t & 1) y = y * b % n;
            b = b * b % n;
            t >>= 1;
        }
        t = d;
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && (t & 1) == 0) return false;
    }
    return true;
}
vector<int> gd_spf(int num) {
    vector<int> divs = {1};
    while (num > 1) {
        int p = spf[num], cnt = 0;
        while (num % p == 0) {
            num /= p;
            cnt++;
        }
        int sz = divs.size();
        for (int i = 0; i < sz; i++) {
            int cur = divs[i];
            for (int j = 1; j <= cnt; j++) {
                cur *= p;
                divs.push_back(cur);
            }
        }
    }
    return divs;
}
vector<int> gd(const int n) {
    vector<int> v;
    for (int i = 1; int64_t(i) * i <= n; i++) {
        if (n % i == 0) {
            v.push_back(i);
            if (i != n / i) v.push_back(n / i);
        }
    }
    return v;
} // not sorted

int32_t main() {
    cin.tie(0)->sync_with_stdio(false);

    prime(40000);

    int32_t Case = 1;    cin >> Case;
    for (int T = 1; T <= Case; T++) {

        int64_t n, k; cin >> n >> k;
        if(is_prime(n)) {
            if(k & 1) {
                cout << n * n << '\n';
            }
            else cout << n << '\n';
            continue;
        }
        vector<int64_t> val;
        for(const int64_t i : pr) {
            if(i * i > n) break;
            while(n % i == 0) {
                val.push_back(i);
                n /= i;
            }
        }
        if(n > 1) val.push_back(n);
        int cnt = min<int64_t>(12, k);
        for(int i = 1; i <= cnt; i++) {
            if(i & 1) {
                val.push_back(val.front());
            }
            else {
                val.pop_back();
            }
            sort(val.begin(), val.end());
        }
        if(k > 12 and k & 1) {
            val.push_back(val.front());
        }
        int64_t ans = 1;
        for(const int64_t i : val) {
            ans *= i;
        }
        cout << ans << '\n';
    }
    return 0;
}