#include<fstream>
using namespace std;
#define MAX 1000002
ifstream in("divprim.in");
ofstream out("divprim.out");
int phi[MAX];
int sol[MAX][9];
int main ()
{
	int i,j;
	//for(i=2;i<=MAX/2;i++)
	//	phi[i<<1]++;
	for(i=3;i<=MAX;i+=2)
	{
		if(phi[i]==0)
			for(j=2*i;j<=MAX;j+=i)
				phi[j]++;
		phi[i+1]++;
	}
	for(i=1;i<=MAX;i++)
	{
		for(j=0;j<=7;j++)
			sol[i][j]=sol[i-1][j];
		sol[i][phi[i]]=i;
	}
	int T;
	in>>T;
	while(T--)
	{
		in>>i>>j;
		out<<sol[i][j]<<'\n';
	}
}