#include <stdio.h>
#define DIM 1000010

int nrPrime[DIM], nrDivPrim[DIM], sol[DIM][8];

void erathostene(int n=1000001) {
	int i, j;
	for (i=2; i <= n; ++i)
	  if (!nrPrime[i])
		for (j=2; i*j<=n; ++j)
			nrPrime[i*j]=1, nrDivPrim[i*j]++;

   /*for (i=i-1; i<=n; ++i)
      if (!nrPrime[i])
         for (j=2; i*j<=n; ++j) nrDivPrim[i*j]++;  */
}


int main() {
	int T, n, k, i, j;

	erathostene();

	FILE *f=fopen ("divprim.in", "r");
	FILE *g=fopen ("divprim.out", "w");
	fscanf(f, "%d", &T);


   sol[1][0]=1;
   for (i=2; i<=1000000; ++i) {
      for (j=0; j<8; ++j)
         sol[i][j] = sol[i-1][j];
      //for (j=0; j<8; ++j)
      sol[i][nrDivPrim[i] + 1-nrPrime[i]] = i;
   }

	while (T--) {
		fscanf(f, "%d %d", &n, &k);
		fprintf(g, "%d\n", sol[n][k]);
	}
	fclose(f);
	fclose(g);
	return 0;
}