#include <stdio.h>
#define Nmax 1000003

int i, j, t;
char p[Nmax];
int divp[Nmax], sol[8][Nmax];

int main() {
	
	FILE *f = fopen("divprim.in", "r");
	FILE *g = fopen("divprim.out", "w");
	
	for (i = 2; i <= Nmax; i++)
		if (!p[i]) {
			divp[i]++;
			for (j = 2*i; j <= Nmax; j += i)
				divp[j]++, p[j] = 1;
		}
	
	for (j = 1; j <= Nmax; j++) {
		for (i = 0; i <= 7; i++)
			sol[i][j] = sol[i][j-1];
		sol[ divp[j] ][j] = j;
	}
	
	fscanf(f, "%d", &t);
	for (; t > 0; t--) {
		fscanf(f, "%d %d", &j, &i);
		fprintf(g, "%d\n", sol[i][j]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}