// Write nodeour code here
#include <bits/stdc++.h>

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define mp make_pair
#define pb(a) push_back(a)
#define pp pop_back()
#define all(v) (v.begin(), v.end())
#define alar (a + 1, a + 1 + n)
#define ff first
#define ss second
#define sz(a) (int)(a.size())
#define ffor(i, a, b) for (int i = a; i <= b; i++)
#define rloop(i, c, d) for (int i = c; i >= d; i--)
#define ll long long
#define vc vector<ll>
#define pii pair<ll, ll>
#define mii map<ll, ll>
#define mod 1000000007
#define MAX 100000
#define endl "\n"
#define o(x) cout << x << endl
using namespace std;
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int mod2 = 998244353;
void solve()
{
               ll x;
               int p;
               cin >> x >> p;

               ll ans = x;
 
               rloop(i, 100000, 1)
               {
                              ll val = 1;
                              bool flag = true;
                              ffor(j, 1, p)
                              {
                                             if (val * i * 1LL > x)
                                             {
                                                            flag = false;
                                                            break;
                                             }
                                             val = val * i * 1LL;
                              }
                              if (flag)
                              {
                                             ll store = (1LL * (val * (x / (__gcd(x, val)))));
                                             ll val1 = __gcd(val, x);
                                             if ((store)% val1 == 0)

                                             {
                                                            ans = min(ans, store/val1);
                                                          //  x = ans;
                                             }
                              }
               }
               if (p == 1)
               {
                              o(1);
                              return;
               }
               o(ans);
}

int main()
{
               ios_base::sync_with_stdio(false);
               cin.tie(NULL);
               cout.tie(NULL);
               int t;
               cin >> t;
               ffor(l, 1, t)
               {
                              // cout << "Case #" << l << ":"
                              //      << " ";
                              solve();
               }
               return 0;
}