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