#include <fstream>
#define Max 1000000
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");

int n,k,t,v[Max],sol[Max][8];

void precompute ()
{
  for (int i=2; i<=Max; i++)
	if (v[i]==0)
	  for (int j=i; j<=Max; j += i )
		v[j]++;
  for (int i=1; i<=Max; i++)
	for (int j=1; j<=7; j++)
	  {
		if (v[i]==j)
		sol[i][j]=i;
		else sol[i][j]=sol[i-1][j];
	  }
	
}

int main ()
{
  precompute ();
  f>>t;
  for (int i=1; i<=t; i++)
  {
	f>>n>>k;
	g<<sol[n][k]<<'\n';
  }
  f.close (); g.close ();
  return 0;
}