#include <fstream>
#include <algorithm>

using namespace std;

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

#define DIM 1000000
#define KMAX 7

int t, n, k;
int ciur[DIM + 1];
int dp[DIM + 1][KMAX + 1];

int main() {

  //aflu pentru fiecare numar la cati factori primi se imparte;
  ciur[0] = ciur[1] = 0;
  for(int i = 2; i <= DIM; i++)
    if(!ciur[i]) {
      ciur[i] = 1;      //daca e numar prim are doar 1 divizor;
      for(int j = i * 2; j <= DIM; j += i)  //ii marchez multiplii;
        ciur[j]++;
    }
  
  //pentru fiecare numar retin cel mai apropiat numar care are k divizori;
  for(int i = 2; i <= DIM; i++)
    for(int j = 1; j <= KMAX; j++)
      if(ciur[i - 1] == j)            //daca numarul de dinainte are exact j divizori
        dp[i][j] = i - 1;             //el devine cel mai apropiat numar cu j divizori;
      else dp[i][j] = dp[i - 1][j];   //ramane acelasi numar;

  fin >> t;
  while(t--) {
    fin >> n >> k;
    fout << dp[n][k] << '\n';
  }

  return 0;
}