#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 1'000'000;
const int MAX_K = 7;

int sol[MAX_N + 1][MAX_K + 1];
int ndp[MAX_N + 1];
int t, n, k;
/// sol[i][j] - cel mai mare numar x <= i cu ndp[x] = j
/// ndp[i] - numarul de divizori primi ai lui i

int main() {
   for (int i = 2; i <= MAX_N; i++)
      if (!ndp[i])
         for (int j = i; j <= MAX_N; j += i)
            ndp[j]++;
   
   for (int i = 2; i <= MAX_N; i++) {
      for (int j = 1; j <= MAX_K; j++)
         sol[i][j] = sol[i - 1][j];
      sol[i][ndp[i]] = i;
   }
   
   fin >> t;
   while (t--) {
      fin >> n >> k;
      fout << sol[n][k] << "\n";
   }
   
   fin.close();
   fout.close();
   return 0;
}