#include <fstream>
#include <vector>
#include <iostream>
 
using namespace std;
 
ifstream in("divprim.in");
ofstream out("divprim.out");
 
int const nmax = 1e6;
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";
}
 
void getgrupe(){
  int igrupa;
  for(int i=1; i<=nmax; i++) {
    igrupa = ndivprim[i];
    grupa[igrupa].push_back(i);
  }
}
 
void solve(int n, int k){
  if(0 < grupa[k].size() && grupa[k][0] <= n) {
    int lastel = grupa[k].size() - 1;
    int pos = cautbin(grupa[k], n, 0, lastel);
    out << grupa[k][pos] << "\n";
  }else{
    out << 0 <<"\n";
  }
}
 
int main()
{
    int ntest, n, k;
    ciur();
    getgrupe();
    in >> ntest;
    for(int i = 0;i < ntest;i++){
      in >> n >> k;
      solve(n, k);
    }
    return 0;
}