// factorize / little bit faster
// https://judge.yosupo.jp/problem/factorize
#include<bits/stdc++.h>

using namespace std;

// https://hitonanode.github.io/cplib-cpp/number/binary_gcd.hpp.html
template <typename Int> Int binary_gcd(Int x_, Int y_) {
  unsigned long long x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;
  if (!x or !y) return x + y;
  int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
  x >>= n, y >>= m;
  while (x != y) {
    if (x > y) {
      x = (x - y) >> __builtin_ctzll(x - y);
    } else {
      y = (y - x) >> __builtin_ctzll(y - x);
    }
  }
  return x << (n > m ? m : n);
}

struct factorizer{
  long long smlrng;
  vector<long long> lpf;
  vector<long long> plis;
  // init
  // https://37zigen.com/linear-sieve/
  factorizer(long long smlrng_){
    smlrng = smlrng_;
    lpf.resize(smlrng+1);
    fill(lpf.begin(),lpf.end(),0);
    plis.clear();
    for(long long i=2;i<=smlrng;i++){
      if(lpf[i]==0){
        lpf[i]=i;
        plis.push_back(i);
      }
      for(auto &p : plis){
        if(p*i > smlrng || p>lpf[i]){break;}
        lpf[p*i]=p;
      }
    }
  }

  vector<long long> tinyplis = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

  long long mulmn(long long a,long long b,long long n){
    __int128 c128=a;
    c128*=b;
    return ((long long)(c128%n));
  }
  long long powmn(long long a,long long b,long long n){
    long long res=1;
    while(b>0){
      if(b&1ll){
        res=mulmn(res,a,n);
      }
      a=mulmn(a,a,n);
      b/=2;
    }
    return res;
  }

  bool isprime(long long n){
    if(n<=1){return false;}
    if(n<=smlrng){return (n==lpf[n]);}
    for(auto &p : tinyplis){
      if(n%p==0){return false;}
    }

    // from now, n should be odd
    // https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
    vector<long long> a={2,7,61};
    if(n>=(1ll<<32)){
      // https://miller-rabin.appspot.com/
      a = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    }

    long long s=__builtin_ctzll(n-1);
    long long d=((n-1)>>s);
    for(auto &ca : a){
      if(ca%n==0){continue;}
      if(powmn(ca,d,n)==1){continue;}
      bool cp=true;
      for(long long r=0;r<s;r++){
        if(powmn(ca,(1ll<<r)*d,n)==(n-1)){cp=false;break;}
      }
      if(cp){return false;}
    }
    return true;
  }

  long long ffrho(long long n){
    long long m=(1ll<<((64-__builtin_clzll(n))/8));
    for(long long c=1;;c++){
      auto f = [&](long long v){ return (mulmn(v,v,n)+c)%n; } ;
      long long x,y=2,r=1,q=1,g=1,ys;
      while(g==1){
        x=y;
        for(long long i=0;i<r;i++){
          y=f(y);
        }
        long long k=0;
        while(k<r && g==1){
          ys=y;
          for(long long i=0;i<min(m,r-k);i++){
            y=f(y);
            q=mulmn(q,abs(x-y),n);
          }
          g=binary_gcd(q,n);
          k+=m;
        }
        r<<=1;
      }
      if(g==n){
        g=1;
        while(g==1){
          ys=f(ys);
          g=binary_gcd(abs(x-ys),n);
        }
      }
      if(g<n){
        if(isprime(g)){return g;}
        else if(isprime(n/g)){return (n/g);}
        return ffrho(g);
      }
    }
  }

  // https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
  vector<long long> factorize(long long n){
    vector<long long> res;
    for(auto &p : tinyplis){
      while(n%p==0){
        n/=p;
        res.push_back(p);
      }
    }
    while(n>1){
      if(isprime(n)){res.push_back(n);break;}
      long long cf=ffrho(n);
      while(n%cf==0){
        n/=cf;
        res.push_back(cf);
      }
    }
    sort(res.begin(),res.end());
    return res;
  }
};

using ll=long long;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  factorizer fz(1000005);
  int t;
  cin >> t;
  while(t>0){
    t--;
    ll x,k;
    cin >> x >> k;
    ll att=0;
    auto ff=fz.factorize(x);
    deque<ll> dq;
    for(auto &nx : ff){
      dq.push_back(nx);
    }
    while(k>0){
      k--;
      att++;
      if(att&1ll){
        dq.push_front(dq[0]);
      }
      else{
        dq.pop_back();
      }
      if(att>=60 && k%2==0){break;}
    }
    ll res=1;
    for(auto &nx : dq){res*=nx;}
    cout << res << "\n";
  }
  return 0;
}