#include <cstdio>

using namespace std;

const int NMAX = 1000000;

int c[NMAX + 5], d[8][NMAX + 5];

void ciur() {
	for(int i = 2; i <= NMAX; ++ i) {
		if(!c[i]) {
			for(int j = i; j <= NMAX; j += i)
				++ c[j];
		}
	}
}

void dnk() {
	for(int i = 1; i <= 7; ++ i) {
		for(int j = 2; j <= NMAX; ++ j) {
			if(c[j] == i)
				d[i][j] = j;
			else
				d[i][j] = d[i][j - 1];
		}
	}
}

int main() {
	freopen("divprim.in", "r", stdin);
	freopen("divprim.out", "w", stdout);

	ciur();
	dnk();

	int t, x, y;
	scanf("%d", &t);

	for(int i = 1; i <= t; ++ i) {
		scanf("%d%d", &x, &y);
		printf("%d\n", d[y][x]);
	}

	return 0;
}