#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;
}