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

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;

    while(t-->0){
        int x, k;
        cin >> x >> k;
        vector<pair<int,int> > vec;
        for(int i = 2; i * i <= x; ++i){
            if(x % i == 0){
                int cnt = 0;
                while(x % i == 0){
                    ++cnt;
                    x /= i;
                }
                vec.push_back({i, cnt});
            }
        }
        if(x > 1)vec.push_back({x, 1});
        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;
}