#include<cstdio>
#include<vector>
#define infile "divprim.in"
#define outfile "divprim.out"
#define nMax 1000013
#define kMax 8

using namespace std;

int divPrim[nMax];
vector <int> numbers[kMax];

void init() {

  for(int i = 2; i < nMax; ++i)
    if(!divPrim[i])
      for(int j = i * 2; j < nMax; j += i)
        ++divPrim[j];

  for(int i = 0; i < nMax; ++i)
    if(divPrim[i] < kMax)
      numbers[divPrim[i]].push_back(i);
}

int binSearch(vector <int> &v, int n) {
  int le = 0, ri = v.size() - 1, res = 0;
  while(le <= ri) {
    int mi = (le + ri) >> 1;
    if(v[mi] <= n) res = v[mi], le = mi + 1;
    else ri = mi - 1;
  }
  return res;
}

void solve() {

  int t, n, k;

  scanf("%d\n", &t);
  while(t--) {
    scanf("%d %d\n", &n, &k);
    printf("%d\n", binSearch(numbers[k], n));
  }

}

int main() {
  freopen(infile, "r", stdin);
  freopen(outfile, "w", stdout);

  init();
  solve();

  fclose(stdin);
  fclose(stdout);
  return 0;
}