#include<fstream>
#define dim 1000000
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int k,p,t,n,i,j,v[1000001][9],a[1000010];
int main()
{
	for(i=2;i<=dim;++i)
		if(a[i]==0)
	for(j=i;j<=dim;j=j+i)
			a[j]++;
	for(i=2;i<=dim;++i)
		if(a[i]<=7)
			v[i][a[i]]=i;
	for(i=2;i<=dim;++i)
		for(j=1;j<=8;++j)
			if(v[i][j]==0)
				v[i][j]=v[i-1][j];
	f>>t;
	for(i=1;i<=t;++i)
	{
		f>>p>>k;
		g<<v[p][k]<<'\n';
	}
	return 0;
}