#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;
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+=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;

    }fo<<p<<'\n';
}
}