#include<fstream>




#include <vector>


#include <iostream>






using namespace std;






ifstream in("divprim.in");


ofstream out("divprim.out");






int const nmax = 30;


int ndivprim[1 + nmax];






void ciur() {


 for(int i = 2; i <= nmax; i++) {


   if(ndivprim[i] == 0) {


     for(int j = i; j <= nmax; j+= i){


       ndivprim[j]++;


     }


   }


 }


}






int v[1 + nmax];






//from indeplineste conditiile iar despre to nu stim nimic


int cautbin(vector<int> &g, int caut, int from, int to) {


   if(from == to){


      return  from;


   } else {


      int mid = (from + to + 1)/2;


      if(g[mid] <= caut)


        return cautbin(g, caut, mid, to); //(1, 2) => (2, 2)


      else


       return cautbin(g, caut, from, mid - 1); //(1, 2) => (1, 1)


   }


}






vector<int> grupa[1 + nmax];










void printgrupe(int ng) {


 for(int i=0; i<=ng; i++) {


   cout<<"grupa["<<i<<"] = {";


   for(int j=0; j < grupa[i].size() - 1; j++)


       cout << grupa[i][j] << ", ";


   int lastIndex = grupa[i].size() - 1;


   if(0 <= lastIndex)


     cout << grupa[i][lastIndex];


   cout << "}\n";


 }


 cout<<"\n";


}






int main()


{


   int grupamax = 0, ntest, n, k;






//from indeplineste conditi


   ciur();


   for(int i=1; i<=nmax; i++) {


     int igrupa = ndivprim[i];


     grupa[igrupa].push_back(i);


     if(grupamax < igrupa)


       grupamax = igrupa;


     //printgrupe(grupamax);


   }


   in >> ntest;


   for(int i = 0;i < ntest;i++){


       in >> n >> k;


       //cout<<n<<" "<<k<<"\n";


       //printgrupe(min(grupamax, k));


       if(k <= grupamax && 0 < grupa[k].size() && grupa[k][0] <= n) {


         int lastel = grupa[k].size() - 1;


         if(grupa[k][lastel] <= n)


           out << grupa[k][lastel] << "\n";


         else {


           int pos = cautbin(grupa[k] , n, 0, lastel);
           //in mod normal nu trebuie sa facem asta, dar acum debuggam
           if(grupa[k][pos] > n) {
             while(grupa[k][pos] > n)
               pos--;
           } else {
             while(grupa[k][pos+1] <=n)
               pos++;
           }


           out << grupa[k][pos] << "\n";


         }


       } else {


         out << 0 <<"\n";


       }


   }


   return 0;


}