#include<fstream.h>
ifstream intrare("divprim.in");
ofstream iesire("divprim.out");
long n,maxim;
int t,k;
int sol[1000001];
long testen[100001];
short int testek[100001];
void citeste()
{
	intrare>>t;
	maxim=1;
	for(long int i=1;i<=t;i++)
	{
		intrare>>testen[i]>>testek[i];
		if(maxim<testen[i])maxim=testen[i];
	}
}

void initiaza()
{
	for(long int i=2;i<=maxim;i++)
	{
		if(sol[i]==0)
		{
			sol[i]=1;
			for(long int j=i+i;j<=maxim;j+=i)
				sol[j]++;
		}
	}
}
void face_test()
{
	for(long int i=n;i>=2;i--)
	{
		if(sol[i]==k){iesire<<i<<"\n";i=0;}
	}
}
int main()
{
	citeste();
	initiaza();
	for(int i=1;i<=t;i++)
	{
		k=testek[i];
		n=testen[i];
		if(k==0)iesire<<"1\n";
		else if(k==1&&n>=2) face_test();
		else if(k==2&&n>=6)face_test();
		else if(k==3&&n>=30)face_test();
		else if(k==4&&n>=210)face_test();
		else if(k==5&&n>=2310)face_test();
		else if(k==6&&n>=30030)face_test();
		else if(k==7&&n>=510510)face_test();
		else iesire<<"0\n";
	}
	return 0;
}