#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");

const int nmax= 1000000, kmax= 7;
int t;
int v[nmax+1], sol[nmax+1][kmax+1];

int main(){
	int player_unu=0;

	for (int i= 2; i<=nmax; i+= 2)
	{        
		++v[i];
	}

	for (int i= 3; i<=nmax; i+= 2)
	{
		if (v[i]==0)
		{
			for (int j= i; j<=nmax; j+= i)
			{
				++v[j];
			}        
		}
	}

	sol[1][0]= 1;
	for (int i= 2; i<=nmax; ++i)
	{
		for (int j= 0; j<=7; ++j)
		{
			sol[i][j]= sol[i-1][j];
		} 
		sol[i][v[i]]= i;
	}

	in>>t;
	for (int i= 0; i<t; ++i)
	{
		int x, y;
		in>>x>>y;
		out<<sol[x][y]<<"\n";
	}

	return player_unu;
}