#include<fstream>

#define NMAX 1000002

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int divs[NMAX],matrix[NMAX][7];

void ciur()
{
	for(int i=2;i<NMAX;i++)
	{
		if(!divs[i])
		{
			for(int j=i+i;j<NMAX;j+=i)
				divs[j]++;
			divs[i]=1;
		}
		for(int j=0;j<7;j++)
			matrix[i][j]=matrix[i-1][j];
		matrix[i][divs[i]-1]=i;
	}
}

int main()
{
	int n,k,t;
	ciur();
	fin>>t;
	while(t--)
	{
		fin>>n>>k;
		fout<<matrix[n][k-1]<<'\n';
	}
	return 0;
}