#include<fstream.h>

long huge ok[1299734];
long i,j,n,t,k,d,x;

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