#include<fstream.h>

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int diviz[1000000];

 int prim(unsigned long n)
  {
               if(n%2==0) return 0;
               for( unsigned long i=3; i*i<=n; i++) 
                  if(n%i==0) return 0;
               return 1;
  }

 int numardiv(unsigned long n)
   {
                       
                       int cont=0;
                       if(diviz[n]) cont++; 
                       for(unsigned long i=2; i<=n/2; i++)
                           if ( diviz[i] && (n%i==0) )cont++; 
                       return cont;
   }    
  
int main()
 {  
        unsigned long n,t,i,j;
        int k;
        diviz[0]=diviz[1]=0;
        diviz[2]=1;
        diviz[3]=1;
        for(i=4; i<=1000000; i++) 
            if(prim(i)) diviz[i]=1; else diviz[i]=0;
        fin>>t;    
        for(i=1; i<=t;i++) 
          {
                 fin>>n>>k;
                 for(j=n; j>0; j-- ) if( numardiv(j)==k ) { fout<<j<<" "; break; }
                 if(j==0) fout<<0;
                 fout<<"\n";
          }    
        return 0;
 }