/*
 *   BISMILLAHIR RAHMANIR RAHIM
 *   ==========================
 *
 *   Submitted By: SAKLAN
 *   North East University Bangladesh



 */

#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;

#define int long long
#define ll long long
#define ld long double
#define pb(a) push_back(a);
#define cinv(v) for(auto &i:v) cin >> i;
#define vi vector<int>
#define vii vector<ll>
#define modd 1000000007
#define coutv(v) for(auto e:v) cout << e << ' ';
#define srt(v) sort(v.begin(),v.end())
#define rsrt(v) sort(v.rbegin(),v.rend())
#define yes cout<<"Yes\n"
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define no cout<<"No\n"
#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))
#define comp [](const pair<int,int> &a, const pair<int,int> &b){ return a.second > b.second; }
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define endl '\n'
#define all(v) (v).begin(),(v).end()
#define saklan ios::sync_with_stdio(0); cin.tie(0);
#define dbg(v) do { \
    for (auto val : v) cout << val << " "; \
    cout << endl << "___________________________ " << endl; \
} while(0)

#define otp(v) do { \
    for (auto val : v) cout << val << " "; \
    cout << endl; \
} while(0)

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



//template<class T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_nodde_update>;

bool cmp(const pair<ll,ll> &a, const pair<ll,ll> &b) {
    return (a.first - a.second) > (b.first - b.second);
}

bool cmpp(const pair<int,int>& a, const pair<int,int>& b){
    if (a.first != b.first) return a.first < b.first;
    return a.second > b.second;
}

int nCr(int n, int r) {
    if (r > n) return 0;
    if (r > n - r) r = n - r;

    int res = 1;
    for (int i = 0; i < r; i++) {
        res = res * (n - i) / (i + 1);
    }
    return res;
}

const int mx = 10000000 + 5;
bool isPrime[mx];

void sieve() {
    isPrime[2] = 1;
    for (int i = 3; i < mx; i += 2)
        isPrime[i] = 1;

    int sq = sqrt(mx);
    for (int i = 3; i <= sq; i += 2) {
        if (isPrime[i]) {
            for (int j = i * i; j < mx; j += 2 * i)
                isPrime[j] = 0;
        }
    }
}


int mindiv(int n){
    for(int i = 2;  i * i <= n; i++){
        if(n%i==0){
            if(isPrime[i]){
                return i;
            }
        }
    }
}

int maxdiv(int n){
    int k = sqrt(n);
    for(int i = k;  i > 1; i--){
        if(n%i==0){
            if(isPrime[i]){
                return i;
            }
        }
    }
}


void solve(){
    int n,k;cin >> n >>k;
    if(k==1){
        cout << n*2<< endl;
        return;
    }
    for(int i = 1; i <=k; i++){
        if(i%2){
            int temp = mindiv(n);
            n *=temp;
        }else{
            int temp = maxdiv(n);
            n/=temp;
        }
    }

    cout << n << endl;
}


int32_t main() {
    saklan
    #ifndef ONLINE_JUDGE
        //freopen("input.txt", "r", stdin);
    #endif
    int t = 1;
    sieve();
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}