#include<fstream>
using namespace std;
int T,n,K,nrdprim[1000100],sol[8][1000100];

int main()
{
	int i,j;
	for(j=2;j<=1000000;j+=2)
		nrdprim[j]=1;
	for(i=3;i<=1000000;i+=2)
	{
		if(nrdprim[i]==0)
		{
			for(j=i;j<=1000000;j+=i)
				nrdprim[j]++;
		}
	}
	for(i=1;i<=1000000;i++)
	{
		for(j=0;j<=7;j++)
			sol[j][i]=sol[j][i-1];
		sol[nrdprim[i]][i]=i;
	}
	
	ifstream fin("divprim.in");
	ofstream fout("divprim.out");
	fin>>T;
	while(T--)
	{
		fin>>n>>K;
		fout<<sol[K][n]<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}