#include <stdio.h>
#define NMAX 1000000
int div[NMAX+1]; // un vector care pastreaza numarul de divizori pentru fiecare numar in intervalul [1, NMAX]
int main(){
  int d, i, t, n, k, x;
  FILE *fin, *fout;
  for(d=2;d<=NMAX;d++)
    if(div[d]==0)
      for(i=d; i<=NMAX; i=i+d)
        div[i]++;
  fin=fopen("divprim.in", "r");
  fout=fopen("divprim.out", "w");
  fscanf(fin, "%d", &t);
  for(i=0; i<t; i++){
    fscanf(fin, "%d%d", &n, &k);
    x=n-1;
    while(x>0 && div[x]!=k)
      x--;
    fprintf(fout, "%d\n", x);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}