#include<fstream>
#define N 1000001


using namespace std;

ifstream f ("divprim.in");
ofstream g ("divprim.out");

int n, i, k, x, ok, ap[ N ], j, a[ 1000001 ][ 8 ];

int main(){

    ap[ 1 ] = 0;
    for( i = 2; i <= 1000000; ++i ){
        if( ap[ i ] == 0 ){
            for( j = 1; i * j <= 1000000; ++j )ap[ i * j ]++;
        }
    }
    for( i = 1; i <= 1000000; ++i )
        for( j = 0; j <= 7; ++j ){
            if( ap[ i ] == j )a[ i ][ j ] = i;
            else a[ i ][ j ] = a[ i - 1 ][ j ];
        }
    f >> n;
    for( i = 1; i <= n; ++i ){
        f >> x >> k;
        g << a[ x ][ k ] << "\n";
    }
    return 0;
}