#include<fstream.h>

long long ok[1299743];
long i,j,n,t,k,d,x,y;

int main()
{	ifstream fin("divprim.in");
	ofstream fout("divprim.out");
	for(i=2;i*i<=1299743;i++)
		if(!ok[i])
		{	j=2;
			while(i*j<=1299743)
			{	ok[i*j]=1;
				j++;
			}
		}
	fin>>t;
	for(y=1;y<=t;y++)
	{       fin>>n>>k;
		for(j=n;j>=2;j--)
		{	d=2;x=k;
			while(d<=i/2&&x>=1)
			{	if(!ok[d]&&i%d==0) x--;
				d++;
			}
			if(x==1)
			{fout<<i<<'\n';break;}
		}
		if(x!=1) fout<<0<<'\n';
	}
	fin.close();
	fout.close();
	return 1;
}