#include <fstream>
using namespace std;

#define Nmax 1000001

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(){
    ifstream fin ( "divprim.in" );
    ofstream fout ( "divprim.out" );

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

   fin >> T;

    for ( ; T ; -- T ){
        fin >> N >> K;
        fout << sol[N][K] << "\n";
    }
    return 0;
}