#include<fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int phi[1000000];
int main ()
{
	int i,j;
	for(i=4;i<=1000000;i+=2)
		phi[i]++;
	for(i=3;i*i<=1000000;i+=2)
		if(phi[i]==0)
			for(j=2*i;j<=1000000;j+=i)
				phi[j]++;
	//for(i=1;i<=100;i++)out<<phi[i]<<'\n';return 0;
	int T,n,k;
	in>>T;
	while(T--)
	{
		in>>n>>k;
		while(phi[n]!=k&&n>0)
			n--;
		out<<n<<'\n';
	}
}