#include<fstream.h>

long sol[1000001],t,i,j,a,b;

int main()
{
	ifstream f("divprim.in");
	ofstream g("divprim.out");


	f>>t;

	for(i=2;i<=1000000;i++)
		if(sol[i]==0)
			for(j=i+i;j<=1000000;j=j+i)
				sol[j]++;
	for(i=1;i<=t;i++)
		{
		f>>a>>b;
		for(j=a;j>=1;j--)
			if(sol[j]==b)
				{
				g<<j<<"\n";
				break;
				}
		if(j==0)
			g<<"0\n" ;
		}
	return 0;
}