#include<cstdio>

#define NMAX 1000005

FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");

using namespace std;

int tests;
int a,b,Answer;
int ciur[NMAX],DP[NMAX][7];

void Preprocess_Eratostene ( void )
{
    for(int i(2) ; i <= NMAX; ++i )
    if( !ciur[i] )
  {
      ++ciur[i];
      for(int ii(i+i) ; ii <= NMAX ; ii+=i )
        ++ciur[ii];
  }
}
void Preprocess_Dynamics ( void )
{
    for(int i(1) ; i <=  NMAX ; ++i )
        for(int ii(1) ; ii <= 7 ; ++ii )
           if( ciur[i] == ii  )
           DP[i][ii]=i;
    else
        DP[i][ii]=DP[i-1][ii];

}
void Write( int nr1 , int nr2 )
{
    if( nr2 > 7 )
     {
         fprintf(g,"0");
        return ;
     }
    fprintf(g,"%d\n",DP[nr1][nr2]);
}
int main ( void )
{
    fscanf(f,"%d",&tests);
    Preprocess_Eratostene();
    Preprocess_Dynamics();
    for(;tests;--tests)
    {
        fscanf(f,"%d%d",&a,&b);
        Write(a,b);
    }
  fclose(f);
  fclose(g);
  return 0;
}