#include <stdio.h>

#define dim 1000001

long ciur[dim];  // in ciur - calculez numarul de divizori primi

long T, N, K;

long sol[dim][8];


int main()
{
   long i, j;

 
   
   freopen("divprim.in","r",stdin);
   freopen("divprim.out","w",stdout);


   for(i=2;i<=dim;i++)
       if(!ciur[i])
       {
            ++ ciur[i];       
            for(j=2*i;j<=dim;j+=i)
                 ++ ciur[j]; 
      }
   
   scanf("%ld",&T);
   
   // sol[i][j] = cel mai mare numar mai mic decat i cu exact j divizori
   
   for ( i = 2; i <= dim; ++ i )
       for ( j = 1; j <= 7; j ++ )
       {

           if ( j == ciur[i] )
              sol[i][j] = i;
           else    
              sol[i][j] = sol[i-1][j];
       }
       
   for ( ;T; -- T)
   {
              scanf("%ld%ld",&N,&K);
              printf("%ld\n",sol[N][K]);
   } 
   return 0;
}