#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";
	}
	f.close();
	g.close();
	return 0;
}