#include <fstream>
#include <vector>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
vector <int> v;
int n,x,dv=1,cnt,i,j,d,p,nr,ans[1500005][8],k,mx,a,b,mx2;
int ciur[2000005];
int main()
{cin>>n;
ciur[1]=0;
for (i=2; i*i<=1000000; i++)
{
    if (ciur[i]==0)
    {
        v.push_back(i);
        for (j=i; j<=1000000; j+=i) ciur[j]++;
    }
}
//for (i=1; i<=1000; i++) cout<<ciur[i]<<' ';
for (k=0; k<=7; k++)
{
    for (i=1; i<=1000000; i++)
    {
        if (ciur[i]==k) {mx2=i;}
        ans[i][k]=mx2;
    }
    mx2=0;
}
for (i=1; i<=n; i++) {cin>>a>>b; cout<<ans[a][b]<<'\n';}
    return 0;
}