#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);
            out << grupa[k][pos] << "\n";
          }
        } else {
          out << 0 <<"\n";
        }
    }
    return 0;
}