#include <cstdio>
using namespace std;

#define Nmax 1000001

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

int ap[Nmax], sol[Nmax][8];

void ciur (){

    for ( int i = 2; i <= Nmax; ++i ){
        if ( !ap[i] ){
            for ( int j = i; j <= Nmax; j += i )
                ap[j]++;
        }
    }
}

int main(){

    int T, N, K;

    ciur();

    for ( int i = 1; i < Nmax; ++i ){
        for ( int j = 1; j <= 7; ++j ){
            sol[i][j] = sol[i-1][j];
            sol[i][ap[i]] = i;
        }
    }

    fscanf ( f, "%d", &T );

    for ( ; T ; -- T ){
        fscanf ( f, "%d%d", &N, &K );
        fprintf ( g, "%d\n", sol[N][K] );
    }
    return 0;
}