#include<fstream.h>
#include<iostream.h>
int prim(int x)
{int i,pr=1,d;
for(i=2;i<=x/2;i++)
	if(x%d==0) {pr=0;
		    break;}
return pr;
}
int main()
{int n,k,d,nd=0,i,j,t,p=0,sol;
ifstream in("divprim.in");
ofstream out("divprim.out");
in>>t;
for(i=1;i<=t;i++)
{in>>n>>k;
for(j=n;j>=2;j--)
       {nd=0;
       for(d=2;d<=j/2;d++)
	      {if(j%d==0 && prim(d)==1) nd++;
	      if(nd>k) break;}
       if(nd==k) {sol=j;
		  break;}

       }
out<<sol<<endl;
sol=0;
}
out.close();
return 0;
}