#include <fstream>
using namespace std;

const int N=1000000;
int v[1<<20],a[1<<20][1<<3],n,k;

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

void ciur()
{
	int i,j;
	for (i=2;i<=N;i++)
		if (!v[i])
			for (j=i;j<=N;j+=i)
				v[j]++;
	for (i=1;i<=N;i++)
	{
		a[i][v[i]]=i;
		for (j=1;j<8;j++)
			a[i][j]=max(a[i][j],a[i-1][j]);
	}
}

int main()
{
	int t,n,k;
	in>>t;
	ciur();
	while (t--)
	{
		in>>n>>k;
		out<<a[n][k]<<"\n";
	}
	return 0;
}