#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        LL x,k;
        cin>>x>>k;
        map<LL,LL> m;
        for(LL i=2; i*i <= x; i++)
        {
            if(x%i==0)
            {
                int s=0;
                while(x%i==0) x/=i, s++;
                m[i]=s; 
            }
        }
        if(x>1) m[x]=1;

        LL ans=1;
        for(auto &mp:m)
        {
            if(mp.second >= k)
            {
                ans = ans*pow(mp.first,mp.second);
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}