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

int prime[100000];
int cntPrime;
int pr[100000];

void precalc(){

    for(int i = 2; i <= 31622; ++i){
        if(!pr[i]){
            prime[++cntPrime] = i;
            for(int j = i * i; j <= 31622; j += i){
                pr[j] = 1;
            }
        }
    }

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

  //  freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

    int t;
    cin >> t;

    precalc();

    while(t-->0){
        int x, k;
        cin >> x >> k;
        vector<pair<int,int> > vec;

        for(int i = 1; i <= cntPrime && prime[i] * prime[i] <= x; ++i){
            int j = prime[i];
            if(x % j == 0){
                int cnt = 0;
                while(x % j == 0){
                    ++cnt;
                    x /= j;
                }
                vec.push_back({j, cnt});
            }
        }
        if(x > 1)vec.push_back({x, 1});
        if(vec.size() == 1){
            if(k & 1)vec[0].second++;
        }else{
        for(int i = 1; i <= k; ++i){
            if(i & 1){
                vec[0].second++;
            }else{
                vec[vec.size() - 1].second--;
                if(vec[vec.size() - 1].second == 0){
                    vec.erase(vec.begin() + vec.size() - 1);
                    if(vec.size() == 1){
                        if(k & 1)vec[0].second++;
                        break;
                    }
                }
            }
        }
        }
        x = 1;
        for(int i = 0; i < vec.size(); ++i){
            for(int j = 0; j < vec[i].second; ++j){
                x *= vec[i].first;
            }
        }
        cout << x << '\n';
    }

    return 0;
}