#include<fstream>
#include<math.h>

using namespace std;

long int t,n,b[100];
int k,p,u;
int main()
{
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
int i,j,z,f,g;

    fin>>t;
   for(i = 1; i <= t; i++)
    {
          fin>>n>>k;
          for(j = n-1; j >=1; j--)
          {
                for(z = 2; z <= j/2; z++)
                      if(j%z == 0)
                      b[u++]= z;
                  for(g = 0; g < u; g++)
                  {   
                      if(b[g] == 2)p++;
                      if(b[g] == 3)p++;
                      if(b[g] == 5)p++;
                      else 
                 for(f = 5; f <= b[g]/2; f+2)
                 if(b[g]%f != 0)
                 p++;
      
                  }         
                if(p == k)
                {
                     fout<<j<<"\n";
                     p = 0;
                     break;
                     
                }
       else if(p != k && j == 1 )
             {
                      fout<<0<<"\n";     
                     p = 0; 
             }             
        else 
          {
           for(g = 0; g < u; g++)
           b[g] = 0;
          p = 0;
          }        
        }
     }
       fin.close();
       fout.close();
       
       return 0;

}