#include <stdio.h>
#define VALMAX 1000000

int c[VALMAX + 1];

void ciur() {
  int i, j;
  for (i = 2; i <= VALMAX;  i++)
    if (c[i] == 0)
      for (j = i; j <= VALMAX; j += i)
        c[j]++;
}


int main() {
  FILE *fin, *fout;
  int t, n, k, nr;
  fin = fopen("divprim.in", "r");
  fscanf(fin, "%d", &t);

  ciur(n);
  fout = fopen("divprim.out", "w");
  while (t--) {
    fscanf(fin, "%d%d", &n, &k);
    while (n > 0 && c[n] != k)
      n--;
    fprintf(fout, "%d\n", n);
  }

  fclose( fin );
  fclose( fout );
  return 0;
}