#include<fstream.h>
long N,K,T;
int sir(int N,int K){
for (long i=N;i>1;i--){
long x=i,nr=0;
if (x%2==0)
  nr=1;
while (x%2==0)
   x/=2;
   for (long d=3;d<=x/d;d+=2)
       if (x%d==0){
	  nr++;
      while (x%d==0)
	   x/=d;  }
   if (x!=1)
       nr++;
if (nr==K)
   return i;     }
return 0;
}
void citire(){
ifstream fin("divprim.in");
ofstream fout("divprim.out");
fin>>T;
for (long i=0;i<T;i++){
    fin>>N>>K;
    fout<<sir(N,K);
    fout<<"\n";}
fin.close();
fout.close();
}
int main(){
citire();
return 0;
}