#include<fstream>
#define dmax 1000010
#define nmax 1000000
using namespace std;

int n,k;
int nrdiviz[dmax];
int sol[dmax][8];

ofstream fout("divprim.out");


void afisare()
{
 if (sol[n][k] == 0 && k==0)
	 fout<<"1"<<'\n'; else
	 fout<<sol[n][k]<<'\n';
}


void citire()
{
 int t,i;
	
 ifstream fin("divprim.in");
 
 fin>>t;
 for (i=1; i<=t; i++)
	 {
	  fin>>n>>k;
	  
	  afisare();
	 }
}


void ciur()
{
 long long i,j;
	
 for (i=2; i<=nmax; i++)
	 {
	  if (nrdiviz[i] == 0) /*daca i este prim*/
		  for (j=i; j<=nmax; j=j+i)
			  nrdiviz[j]++;
	 
	  for (j=0; j<=7; j++) /*copii linia i-1 in linia i*/
		  sol[i][j] = sol[i-1][j];
	  
	  if (nrdiviz[j] <= 7) /*actualizez daca este cazul linia i*/
		  sol[i][nrdiviz[i]] = i;
	 }
}


int main()
{
	
 ciur();
 citire();
 
 fout.close();
	
 return 0;
}