#include <stdio.h>

long T, K, N;
long nrdiv[1000001];

void ciur() {
	long i, j, sqr = 1000;
	nrdiv[1] = nrdiv[0] = -1;
	nrdiv[2] = 1;
	for(i = 4; i <= 1000000; i += 2)
		nrdiv[i]++;
	for(i = 3; i <= sqr; i++)
		if(nrdiv[i] == 0) {
			nrdiv[i]++;
			for(j = 2 * i; j <= 1000000; j += i)
				nrdiv[j]++;
		}
}

int main() {
	long i, j;
	freopen("divprim.in", "r", stdin);
	freopen("divprim.out", "w", stdout);
	ciur();
	scanf("%ld", &T);
	for(i = 1; i <= T; i++) {
		scanf("%ld %ld", &N, &K);
		for(j = N; K != nrdiv[j] && j > 0; j--);
		printf("%ld\n", j);
	}
	return 0;
}