#include<iostream>
#include<cmath>
using namespace std;
int q,cnt;
bool st[100010];
int prime[100010];
//bool ispower(int n)//这个判断质数的方法不可行
//{
// for(int i=2;i*i<=n;i++)
// {
// if(n%i==0)
// return false;
// }
// return true;
//}
//Acwing欧拉线性筛法, 只筛st[prime[j]*i]
// 其中prime[j]是最小质因子
void getprime(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) prime[cnt++]=i;
for(int j=0;i*prime[j]<=n;j++)
{
st[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
int main()
{
cin>>q;
getprime(10000);
for(int i=0;i<q;i++)
{
long long n;
int k;
long long res=1;
scanf("%lld%d",&n,&k);
for(int j=0;j<cnt;j++)//遍历prime
{
int t=prime[j];
if(n%t==0)
{
int cishu=0;
while(n%t==0)
{
cishu++;
n/=t;
}
if(cishu>=k) res*=pow(t,cishu);
}
}
printf("%lld\n",res);
}
return 0;
}