#include <stdio.h>
#define VALMAX 1000000
#define KMAX 7

int c[VALMAX + 1], sol[KMAX + 1][VALMAX + 1];

int maxim(int a, int b) {
  return a > b ? a : b;
}

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);
  for (k = 1; k <= KMAX; k++) {
    for (n = 1; n <= VALMAX; n++) {
      sol[k][n] = maxim( sol[k][n - 1], (c[n] == k) * n );
    }
  }

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

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