#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int DIM = 1000001;
int matrix[DIM][8], t, n, k;

int main() {
    vector<int> sieve(DIM);
    int i, j;
    for (i = 4; i < DIM; i += 2) sieve[i] = 1;
    for (i = 3; i < DIM; i += 2)
        if (!sieve[i]) {
            sieve[i] = 1;
            for (j = 2; j * i < DIM; ++j) ++sieve[j * i];
        }
    for (i = 2; i < DIM; ++i) {
        memcpy(matrix[i], matrix[i - 1], sizeof(matrix[i - 1]));
        if (sieve[i] < 8) matrix[i][sieve[i] - 1] = i;
    }
    for (f >> t; t; --t) {
        f >> n >> k;
        if (!k) g << 0 << '\n';
        else g << matrix[n][--k] << '\n';
    }
    return 0;
}