#include<fstream>

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; j >=1; j--)
          {
                for(z = 2; z <= j/2; z++)
                      if(j%z == 0)
                      b[u++]= z;
                  for(g = 0; g < u; g++)
                  {    
                      for(f = 2; f <= z/2; f++)
                            if(b[g]%f != 0)
                            p++;
                  }         
                if(p == k)
                {
                     fout<<j<<"\n";
                     break;
                }
       else if( p != k)
            {
            fout<<0<<"\n";
           for(g = 0; g < u; g++)
           b[g] = 0;         
           p = 0;
       }
           }
     }
       fin.close();
       fout.close();
       
       return 0;

}