#include<fstream>
using namespace std;
ifstream fi("divprim.in");
ofstream fo("divprim.out");
int e[200002],t,i,ma,j,x[1000001],nr,r[100001];
long long p,h;
int main()
{
fi>>t;
for(i=1;i<=2*t;i++)
    fi>>e[i];
for(i=1;i<=2*t;i=i+2)
    if(e[i]>ma)
    ma=e[i];
for(i=2;i<=ma;i++)
if(!x[i])
    for(j=i+i;j<=ma;j=j+i)
    x[j]+=1;
for(i=1;i<=2*t;i=i+2)
{p=0;
    for(j=e[i];j>=2;j--)
        if(x[j]==e[i+1])
    {p=j;break;

    }if(e[i]==1)
    p=1;
    h++;
    r[h]=p;
}
for(i=1;i<=h;i++)
    fo<<r[i]<<'\n';
fi.close();
fo.close();
}