#include <fstream>
#include <vector>

using namespace std;

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

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

void createMatrix() {
    vector<int> sieve(DIM);
    sieve[0] = sieve[1] = 1;
    int i, j;
    for (i = 2; i < DIM; ++i)
        if (!sieve[i]) {
            for (j = i; j * i < DIM; j += i) ++sieve[j * i];
        }
    for (i = 2; i < DIM; ++i) {
        for (j = 1; j < 8; ++j) matrix[i][j] = matrix[i - 1][j];
        matrix[i][sieve[i]] = i;
    }
    sieve.clear();
}

int main() {
    createMatrix();
    for (f >> t; t; --t) {
        f >> n >> k;
        g << matrix[n][k] << '\n';
    }
    return 0;
}