#include <stdio.h>
#include <string.h>
using namespace std;
FILE *fi,*fo;
int e[200002],t,i,ma,j,x[1000001],nr,r[100001];
int p,h;
int m(int x)
{
    if(x==0)
        return 1;
    else
        return x;
}
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(m(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");}
}