#include <stdio.h>
#include <string.h>
using namespace std;
FILE *fi,*fo;

int e[200002],t,i,ma,j,x[1000001],nr,r[100001];
long long p,h;
int main()
{fi=fopen("divprim.in","r");
fo=fopen("divprim.out","w");
fscanf(fi,"%d",&t);
for(i=1;i<=2*t;i++)
     fscanf(fi,"%d",&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]==0)
    p=1;
    h++;
    r[h]=p;
}
for(i=1;i<=h;i++){
fprintf(fo,"%d",r[i]);
fprintf(fo,"\n");}

}