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