#include <stdio.h>
 
#define in "divprim.in"
#define out "divprim.out"
 
#define TMAX 8
#define NMAX 1000002
 
int T;
int sol[NMAX][7];
int ndp[1000003];
 
void Read();
void Solve();
void Dinamic();
 
FILE *fout = fopen( out, "w" );
 
int main()
{
    Solve();
    Dinamic();     
    Read();   
     
    fclose( fout );
    return 0;
}
 
void Read()
{
     FILE *fin = fopen ( in, "r" );
     fscanf( fin, "%d", &T );
     int i, n, k;
     for ( i = 1; i <= T; ++i )
     {
         fscanf( fin, "%d%d", &n, &k );
         fprintf( fout, "%d\n", sol[n][k] );
     }
      
     fclose( fin );
}
 
void Solve()
{
     int i, j;
     ndp[1] = 0;
     for ( i = 2; i < NMAX; ++i )
     {
         if ( ndp[i] == 0 ) //deci e numar prim
         {
              j = 1;
              while ( i*j <= NMAX )
              {
                    ndp[i*j]++;
                    j++;
              }
         }
     }
}
          
void Dinamic()
{
     int i, j;
     for ( i = 1; i <= TMAX; ++i )
         sol[1][i] = 0;
     for ( i = 2; i <= NMAX; ++i )
     {
         for ( j = 1; j <= TMAX; ++j )
             sol[i][j] = sol[i-1][j];
         sol[i][ndp[i]] = i;
     }
}