#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
const int NMAX = 1000002;
int v[NMAX + 5];
int dp[NMAX][10];
int T, N, K;
 
void Erathostenes(){
  for(int i = 2; i <= NMAX; ++i){
    if(v[i] == 0){
      v[i]++;
      for(int j = i + i; j <= NMAX; j += i)
        v[j]++;
    }
  }
}
 
void DP(){
  for(int i = 2; i <= NMAX; ++i){
    for(int j = 0; j <= 7; ++j){
      if(v[i] == j)
        dp[i][j] = i;
      else
        dp[i][j] = dp[i - 1][j];
    }
  }
}
 
int main(){
  Erathostenes();
  DP();
  in >> T;
  for(int i = 1; i <= T; ++i){
    in >> N >> K;
    out << dp[N][K] << "\n";
  }
  return 0;
}