#include <stdio.h>

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

void ciur() {
	long i, j, sqr = 1000;
	nrdiv[1] = nrdiv[0] = -1;
	for(i = 4; i <= 1000000; i += 2)
		nrdiv[i]++;
	for(i = 3; i <= sqr; i++)
		if(nrdiv[i] == 0) {
			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();
	for(i = 2; i <= 1000001; i++) {
		for(j = 0; j < 8; j++)
			mat[i][j] = mat[i - 1][j];
		mat[i][nrdiv[i]] = i;
	}
	scanf("%ld", &T);
	for(i = 1; i <= T; i++) {
		scanf("%ld %ld", &N, &K);
		printf("%ld\n", mat[N][K]);
	}
	return 0;
}