#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000000

int ciur[MAXN+1];
int m[8][MAXN],ind[8];

int cautare(int tip, int e){
  int min, max, mij;
  min = 0;
  max = ind[tip];
  while((max - min) > 1){
    mij = (max + min) / 2;
    if(e < m[tip][mij]){
      max = mij;
    }else{
      min = mij;
    }
  }
  return min;
}

int main()
{
    FILE *fin, *fout;
    int i, j, t, n, k, maxkdiv;
    for(i = 2; i <= MAXN; i++){
      if(ciur[i] == 0){
        ciur[i] = 1;
        for(j = i + i; j <= MAXN; j += i){
          ciur[j]++;
        }
      }
    }
    m[0][0] = 1;
    ind[0] = 1;
    for(i = 2; i <= MAXN; i++){
      m[ciur[i]][ind[ciur[i]]] = i;
      ind[ciur[i]]++;
    }
    fin=fopen("divprim.in", "r");
    fscanf(fin, "%d", &t);
    fout=fopen("divprim.out", "w");
    for(i = 0; i < t; i++){
      fscanf(fin, "%d%d", &n, &k);
      maxkdiv = cautare( k , n );
      if(n < m[k][maxkdiv]){
        maxkdiv--;
      }
      if(maxkdiv < 0){
        fprintf(fout, "0\n");
      }else{
        fprintf(fout, "%d\n", m[k][maxkdiv]);
      }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}