/*
Autor:Mihai Tabara
Puncaj: ?
Lang:C++
Prog: divprim 
Link: http://infoarena.ro/arhiva/divprim
*/

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