#include <fstream>
#define ma 1000001

using namespace std;

int NRD[ma];
int REZ[ma][9];

void ciur()
{
	for (int i = 2; i <= ma; ++i)
	{
		if (NRD[i] == 0)
			for (int j = i; j <= ma; j += i)
				++NRD[j];
		for (int j = 1; j <= 8; ++j)
			REZ[i][j] = REZ[i-1][j];
		REZ[i][NRD[i]] = i;
	}
}
int main()
{
	ifstream f ("divprim.in"); ofstream g ("divprim.out");
	int n, x, y;
	ciur();
	f >> n;
	for (int i = 1; i <= n; ++i)
	{
		f >> x >> y;
		g << REZ[x][y] << '\n';
	}
	g.close(); return 0;
}