#include <stdio.h>
#define DIM 1000010

int nrPrime[DIM], nrDivPrim[DIM], sol[8][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, i;
	erathostene(DIM-1);
	FILE *f=fopen ("divprim.in", "r");
	FILE *g=fopen ("divprim.out", "w");
	fscanf(f, "%d", &T);
	for (i=0; i<=7; ++i) sol[i][0]=1;
	for (i=1; i<DIM; ++i) sol[ nrDivPrim[i] ][ ++sol[nrDivPrim[i]][0] ] = i;
	while (T--) {
		fscanf(f, "%d %d", &n, &k);
		i=sol[k][0];
		while (sol[k][i]>n) i--;
		fprintf(g, "%d\n", sol[k][i]);
	}
	fclose(f);
	fclose(g);
	return 0;
}