#include <fstream>
#define NMAX 1000002
using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divprim.out");

int ciur [NMAX+2];
int d[NMAX][10];


int main (){

  int t,n,k;
  fin >> t;

  for (int i = 2; i <= NMAX; ++i){
    if (ciur[i]==0){
      ciur[i]++;
      for (int j = i + i; j <= NMAX; j += i)
        ciur[j]++;
    }
  }

  for (int i = 2; i <= NMAX; ++i)
    for (int j = 1; j <= 7; ++j)
      if (ciur[i] == j)
        d[i][j] = i;
      else d[i][j] = d[i-1][j];

  for (int i = 1; i <= t; ++i){
    fin >> n >> k;
    fout << d[n][k] << "\n";
  }

}