#include <fstream>
#include <string>

using namespace std;

ifstream cin("divprim.in"); ofstream cout("divprim.out");

const int LMAX = 1e6;

int c[LMAX + 5], m[10][LMAX + 5];

void ciur() {
    int last;
    for (int i = 2; i <= LMAX; ++i) {
        if (c[i] == 0) {
            for (int j = i; j <= LMAX; j = j + i) {
                c[j]++;
            }
        }
    }
    for (int i = 1; i <= 7; ++i) {
        last = 0;
        for (int j = 1; j <= LMAX + 5; ++j) {
            if (c[j] == i) {
                last = j;
            }
            m[i][j] = last;
        }
    }
}


int main() {

    ciur();
    int t, n, k, nr;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        cout << m[k][n] << '\n';
    }
    return 0;
}