#include<fstream.h>
int prim(int h){
 if (h==2)
    return 1;
 if (h<2||h%2==0)
     return 0;
	for (int z=3;z<h;z+=2)
	   if (h%z==0)
	      return 0;
	return 1;
   }
int main(){
ifstream fin("divprim.in");
ofstream fout("divprim.out");
unsigned long T;
fin>>T;
for (unsigned long w=0;w<T;w++){
unsigned long  N,K,i=1,a[5000];
long z;
      fin>>N>>K;
      unsigned long M=N;
      a[0]=2;
      for (unsigned long  h=3;h<=M;h+=2){
   if (prim(h)==1)
       a[i++]=z;    }
long nr=0;
unsigned long s=0;
for (unsigned long y=N;y>1;y--){
       nr=0;
    for (long j=0;j<i;j++)
	if (y%a[j]==0)
	    nr++;
    if (nr==K){
	s=y;
       break;} }
fout<<s<<"\n";
}
fin.close();
fout.close();
return 0;
}