#include<fstream>
using namespace std;
ifstream fi("divprim.in");
ofstream fo("divprim.out");
int e[100001],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)
{nr=0;p=0;
    for(j=e[i];j>=1;j--)
    {
        nr=0;
        for(h=2;h<=j;h++)
            if(j%h==0&&!x[h])
            nr++;
        if(nr==e[i+1])
        {
            p=j;
            break;
        }
    }
    fo<<p<<'\n';
}
}