#include<fstream>
#define DIM 1000000
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int w[DIM + 5],t,n,k,x[8][DIM];
void f(){
    for( int i = 2; i <= DIM; i++ ){
        if( w[i] == 0 ){
            for( int j = i; j <= DIM; j += i ){
                w[j]++;
            }
        }
    }
    return;
}
int main(){
    f();
    for( int i = 1; i <= 7; i++ ) {
        for( int j = 2; j <= DIM; j++ ){
            if( w[j] == i ){
                x[i][j] = j;
            }else{
                x[i][j] = x[i][j - 1];
            }
        }
    }
    fin >> t;
    for( ; t != 0; t-- ){
        fin >> n >> k;
        if( k == 0 ){
            fout << "1\n";
            continue;
        }
        fout << x[k][n] << "\n";
    }
    return 0;
}