//! In The Name Of Allah

/*********************************************************************\
*!          |       *        |       | ___  | @                       |
*!          |      * *       |       |  |   |  @                      |
*!          |     *   *      |       |  |   |   @                     |
*!          |    *******     |-------|  |   |    @                    |
*! |*       |   *       *    |       |  |   |   @                     |
*! |        |  *         *   |       |  |   |  @                      |
*! |________| *           *  |       | ___  | @                       |
*!                                                                    |
*!  codeforces = Jahid__Noob                                          |
*!  mail =  [email protected]                                       |
*!  IIT,Jahangirnagar University(51)                                  |
*!                                                                    |
**********************************************************************/

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define pb push_back
#define pob pop_back
#define make M
#define F first
#define S second
#define all(s) (s).begin(), (s).end()
#define rall(s) s.rbegin(), s.rend()
#define sz(x) (int)x.size()
#define mem(a, b) memset(a, b, sizeof(a))
#define cnt_bit(x) __builtin_popcountll(x)
#define getbit(n, i) (((n) & (1LL << (i))) != 0)
#define msb(x) 64 - __builtin_clzll(x)
#define setbit(n, i) ((n) |= (1LL << (i)))
#define hoise cout << "Hoise" << endl;
#define tham getchar();
#define TxtIO                         \
    freopen("sample.in", "r", stdin); \
    freopen("sample.out", "w", stdout);
#define Fokinnir_moto_kaj_koris_na \
    ios_base::sync_with_stdio(0);  \
    cin.tie(0);                    \
    cout.tie(0);
#define py cout << "YES" << endl
#define pn cout << "NO" << endl
#define PI acos(-1)
#define sum_of(A) accumulate(all(A), 0ll)
#define max_of(A) *max_element(all(A))
#define min_of(A) *min_element(all(A))

typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef array<int,3> tu;

ll gcd(ll a, ll b) { return __gcd(a, b); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }

/*
auto Goriber_function = [&] (int m) -> int{

};
*/

const ll oo = 1e18;
const ll mod = 1e9 + 7;
const ll N = sqrt(mod) + 123;

vector<int> primes;
bitset<N>is_prime;

void sieve_v0() {
  for (int i = 3; i < N; i += 2) {
    is_prime[i] = 1;
  }
  for (int i = 3; i * i < N; i += 2) {
    if (is_prime[i]) {
      for (int j = i * i; j < N; j += i) {
        is_prime[j] = 0;
      }
    }
  }
  is_prime[2] = 1;
  for (int i = 2; i < N; i++) {
    if(is_prime[i]){
      primes.push_back(i);
    }
  }
}

void Goriber_solve()
{
    int n,k;
    cin >> n >> k;
    vii p;
    for(auto u : primes){
        if(u * u > n){
            break;
        }
        if(n % u == 0){
            int cnt = 0;
            while(n % u == 0){
                n /= u;
                cnt++;
            }
            p.pb({u,cnt});
        }
    }
    if(n > 1){
        p.pb({n,1});
    }
    if(sz(p) == 1){
        if(k & 1){
            cout << p[0].F * (p[0].S + 1) << endl;
        }
        else{
            cout << p[0].F * (p[0].S) << endl;
        }
        return;
    }
    int la = k / 2;
    for(int i = sz(p) - 1; i >= 1; i--){
        int x = min(la,p[i].S);
        if(x == 0)break;
        la -= x;
        p[i].S -= x;
        p[0].S += x;
    }

    if(k & 1)p[0].S++;
    // for(auto u : p){
    //     cout << u.F << " " << u.S << endl;
    // }
    int ans = 1;
    for(int i = 0; i < sz(p); i++){
        if(p[i].S == 0)break;
        for(int j = 0; j < p[i].S; j++){
            ans *= p[i].F;
        }
    }
    cout << ans << endl;
}

signed main()
{
    Fokinnir_moto_kaj_koris_na
    sieve_v0();
    int _ = 1,tc = 0;
    cin >> _;
    while (_--)
    {
        //cout<<"Case "<<++tc<<": ";
        Goriber_solve();
    }
    return 0;
}