#include<fstream.h>
#include<math.h>
main()
{
ifstream in("divprim.in");
ofstream o("divprim.out");

long t, n, i, k, h, s, sd, d, d2, k2;
in>>t;
for(h=1;h<=t;h++)
{
	in>>n>>k;
	k2=2;
	if(k==2)
		k2=6;
		else
		if(k==3)
			k2=30;
			else
			if(k==4)
				k2=210;
				else
				if(k==5)
					k2=2310;
					else
					if(k==6)
						k2=30030;
						else
						k2=510510;


	for(i=n;i;i--)
		if(i%k2==0)
		{	o<<i<<'\n';
			i=0;
		}


	}



in.close();
o.close();
return 0;
}