#include<fstream>
using namespace std;
ifstream fi("divprim.in");
ofstream fo("divprim.out");
int e[200002],t,i,ma,j,x[1000001],nr,p,h=0,r[100001];
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=2;j<=ma/i;j++)
    x[j*i]+=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;

    }h++;
    r[h]=p;
}
for(i=1;i<=h;i++)
    fo<<r[i]<<'\n';
}