#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=4;i<=1000000;i+=2)
		phi[i]=1;
	for(i=3;i*i<=1000000;i+=2)
	{
		if(phi[i]==0)
			for(j=2*i;j<=1000000;j+=i)
				phi[j]++;
	}
	int n,k;
	for(i=1;i<=1000000;i++)
	{
		for(j=0;j<8;j++)
			sol[i][j]=sol[i-1][j];
		sol[i][phi[i]]=i;
	}
	int T;
	in>>T;
	while(T--)
	{
		in>>n>>k;
		out<<sol[n][k]<<'\n';
	}
}