#include <fstream>

using namespace std;
int ciur[1000000], mat[8][1000000];
int main() {
    ifstream cin ( "divprim.in" );
    ofstream cout ( "divprim.out" );
    int n, a, b, d, i;
    ciur[0] = ciur[1] = 0;
    for ( d = 2; d < 1000000; d++ ) {
        if ( ciur[d] == 0 ) {
            for ( i = d; i <= 1000000; i = i + d )
                ciur[i]++;
        }
        for ( i = 1; i < 8; i++ ) {
            mat[i][d] = mat[i][d - 1];
        }
        if ( ciur[d] < 8 ) {
            mat[ciur[d]][d] = d;
        }
    }
    cin >> n;
    for ( i = 0; i < n; i++ ) {
        cin >> a >> b;
        cout << mat[b][a] << '\n';
    }
    return 0;
}