#include <fstream>
#include <algorithm>
#include <vector>

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];
vector <int> V[KMAX + 1];   

//caut cel mai mare nr care are exact k divizori si este <= n 
static inline int CautBinarDr(int n, int k) {
  int st = 0, dr = V[k].size() - 1, nr = 0;
  while(st <= dr) {
    int mid = (st + dr) >> 1;
    if(V[k][mid] <= n) {
      nr = V[k][mid];
      st = mid + 1;
    }else dr = mid - 1;
  }

  return nr;
}

int main() {
  ciur[0] = ciur[1] = 0; 
  for(int i = 2; i <= DIM; i++)
    if(!ciur[i]) {
      ciur[i] = 1;
      for(int j = i * 2; j <= DIM; j += i)
        ciur[j]++;
  }
  for(int i = 1; i <= DIM; i++)
    V[ciur[i]].push_back(i);  //retin pentru fiecare numar de divizori numerele care au acel nr de div;
  
  fin >> t;
  while(t--) {
    fin >> n >> k;
    fout << CautBinarDr(n, k) << '\n';
  }

  return 0;
}