#include <bits/stdc++.h>

using namespace std;

ifstream fin ("divprim.in");
ofstream fout ("divprim.out");

const int NM = 1e6 + 5;

int d[NM];
vector<int>g[8];

void precalc(){
  for (int i = 2; i < NM; i++){
    if (d[i] == 0){
      for (int j = i; j < NM; j += i){
        d[j] += 1;
      }
    }
  }
  for (int i = 2; i <= (1e6); i++){
    if (d[i] <= 7){
      g[d[i]].push_back(i);
    }
  }
}

int main(){
  ios_base::sync_with_stdio(false);
  precalc();
  int t; fin >> t;
  while (t--){
    int n, k; fin >> n >> k;
    int q = lower_bound(g[k].begin(), g[k].end(), n) - g[k].begin() - 1;
    fout << (q < 0 ? 0 : g[k][q]) << '\n';
  }
}