/*
    JAI JAGANNATH!
*/
//@Author : zanj0

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

// #define LOCAL  // ← enable locally via -DLOCAL; keep commented for OJ
#define ff first
#define ss second
#define pb push_back
#define MOD 1000000007
#define inf 1000000000000000000LL
#define ps(x, y) fixed << setprecision(y) << x
#define w(x)  \
    int x;    \
    cin >> x; \
    while (x--)
#define endl "\n"
#define timetaken cerr << "Time : " << 1000 * (long double)clock() / (long double)CLOCKS_PER_SEC << "ms\n"

typedef long long int lli;

#ifdef LOCAL
#define dbg(x) cerr << "[DBG] " << #x << " = " << (x) << '\n'
template <class A, class B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ',' << p.second << ')'; }
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    for (size_t i = 0; i < v.size(); ++i)
    {
        if (i)
            os << ',';
        os << v[i];
    }
    return os << ']';
}
template <class K, class V>
ostream &operator<<(ostream &os, const map<K, V> &mp)
{
    os << '{';
    bool first = true;
    for (const auto &kv : mp)
    {
        if (!first)
            os << ',';
        first = false;
        os << kv.first << ':' << kv.second;
    }
    return os << '}';
}
template <class K, class V>
ostream &operator<<(ostream &os, const unordered_map<K, V> &mp)
{
    os << '{';
    bool first = true;
    for (const auto &kv : mp)
    {
        if (!first)
            os << ',';
        first = false;
        os << kv.first << ':' << kv.second;
    }
    return os << '}';
}
#else
#define dbg(x) ((void)0)
#endif

void zanj0()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
}

/*
────────────────────────────────────────────────────────────────────────
    Problem Statement:

    Observations:
    6 = 2 * 3

    Number will always get multiplied by smallest prime.



    Claims:

────────────────────────────────────────────────────────────────────────
*/
vector<lli> primes;
void Sieve()
{
    const int N = 31623;
    vector<bool> isPrime(N + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= N; i++)
    {
        if (isPrime[i])
            for (int j = i * i; j <= N; j += i)
                isPrime[j] = false;
    }
    for (int i = 2; i <= N; i++)
        if (isPrime[i])
            primes.push_back(i);
}

vector<pair<lli, int>> Factorize(lli x)
{
    vector<pair<lli, int>> ret;
    for (int p : primes)
    {
        if (1LL * p * p > x)
            break;
        if (x % p == 0)
        {
            int c = 0;
            while (x % p == 0)
            {
                x /= p;
                c++;
            }
            ret.pb({p, c});
        }
    }
    if (x > 1)
        ret.pb({x, 1});
    return ret;
}
lli FastPow(lli base, lli power)
{
    lli ret = 1;
    while (power)
    {
        if (power & 1)
            ret *= base;

        base *= base;
        power >>= 1;
    }
    return ret;
}
void Solve()
{
    lli n, k;
    cin >> n >> k;
    vector<pair<lli, int>> v = Factorize(n);

    dbg(v);

    lli a = (k + 1) / 2;
    lli b = k - a;

    lli big = 0;
    n = v.size();
    for (int i = 1; i < n; i++)
    {
        big += v[i].ss;
    }
    lli ret = 0;
    if (big < b)
    {
        // All big will be removed.
        lli small_cnt = big + (a & 1);
        ret = FastPow(v[0].ff, small_cnt);
    }
    else
    {
        lli now = b;
        for (int i = n - 1; i >= 1 && now; i--)
        {
            lli take = min(now, (lli)v[i].ss);

            v[i].ss -= take;
            now -= take;
        }

        ret = FastPow(v[0].ff, v[0].ss + a);
        for (int i = 1; i < n; i++)
        {
            if (!v[i].ss)
                break;
            ret *= FastPow(v[i].ff, v[i].ss);
        }
    }

    cout << ret << endl;
}

int32_t main()
{
    zanj0();
    Sieve();
    w(t) Solve();
    timetaken;
    return 0;
}

/*
    GOLDEN RULES
    • Solutions are simple.
    • Proofs are simple.
    • Implementations are simple.
*/