#include <fstream>
#define ma 1000001
using namespace std;
int i,j,n,x,y,d;
int NRD[ma];
int REZ[ma][9];

void ciur()
{
	for (i=2;i<=ma;++i)
	{
		if (NRD[i]==0)
			for (j=i;j<=ma;j+=i)
				NRD[j]++;
		for (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");
	ciur();
	f>>n;
	for (i=1;i<=n;i++)
	{
		f>>x>>y;
		g<<REZ[x][y]<<endl;
	}
	f.close();
	g.close();
	return 0;
}