#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin ("divprim.in");
ofstream cout ("divprim.out");

int t, n, k;

int dv[1000005];
vector <int> nr[10];

int main() {
  for(int i = 2; i <= 1000000; i++) {
    if(dv[i] == 0) {
      for(int j = i; j <= 1000000; j += i)
        dv[j]++;
    }
  }
  for(int i = 1; i <= 1000000; i++)
    nr[dv[i]].push_back(i);
  cin >> t;
  for(; t; t--) {
    cin >> n >> k;
    int poz = upper_bound(nr[k].begin(), nr[k].end(), n) - nr[k].begin();
    if(poz)
      cout << nr[k][poz - 1] << "\n";
    else
      cout << "0\n";
  }
  return 0;
}