#include<fstream>
#define NM 1000001
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int a[8][500100],h[10];
int v[1000100],i,j,k,x,t;
int cb()
{
	int st,dr,mij;
	st=1;dr=h[k];
	while(st<=dr)
	{
		mij=(st+dr)>>1;
		if(a[k][mij-1]<=x&&a[k][mij]>x)
			return a[k][mij-1];
		if(x>a[k][mij])
			st=mij+1;
		else
			dr=mij-1;
	}
	return 0;
}
int main ()
{
	f>>t;
	for(i=2;i<=NM;++i)
	{
		if(!v[i])
		{
			v[i]=1;
			for(j=i+i;j<=NM;j+=i)
				v[j]++;
		}
	}
	a[0][1]=1;
	for(i=2;i<=NM;++i)
		if(v[i]<=7)
			a[v[i]][++h[v[i]]]=i;
	while(t--)
	{
		f>>x>>k;
		g<<cb()<<"\n";
	}
	return 0;
}