#include <fstream>
#include <vector>

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;
    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;
        int lastel = grupa[k].size() - 1;
        if(grupa[k][0] <= n){
          out << cautbin(grupa[k] , n, 0, lastel);
        }else{
          out << 0;
        }
    }
    return 0;
}