#include <fstream>
#define DEF 100001

using namespace std;

ifstream fin ("divprim.in");
ofstream fout ("divprim.out");

int t, n, k, ciur[DEF + 1], sol[DEF + 1][8];

int main () {
    fin >> t;
    for (int i = 2; i <= DEF; i++) {
        if (ciur[i] == 0) {
            for (int j = 1; j * i <= DEF; j++) {
                ciur[i * j]++;
            }
        }
    }

    sol[1][0] = 1;
    for (int i = 2; i <= DEF; i++) {
        for (int j = 1; j <= 7; j++) {
            sol[i][j] = sol[i - 1][j];
        }
        sol[i][ciur[i]] = i;
    }

    for (int i = 1; i <= t; i++) {
        fin >> n >> k;
        fout << sol[n][k] << "\n";
    }

    return 0;
}