#include <stdio.h>
#define DIM 1000001

int nrPrime[DIM], nrDivPrim[DIM];

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


int main() {
	int T, n, k;
	erathostene(DIM-1);
	FILE *f=fopen ("divprim.in", "r");
	FILE *g=fopen ("divprim.out", "w");
	fscanf(f, "%d", &T);
	while (T--) {
		fscanf(f, "%d %d", &n, &k);
		while (nrDivPrim[n]!=k && n) n--;
		fprintf(g, "%d\n", n);
	}
	fclose(f);
	fclose(g);
	return 0;
}