#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 1000000;

vector<int> sieve(int max) {
    vector<int> prime_factors_count(max + 1, 0);
    for (int i = 2; i <= max; ++i) {
        if (prime_factors_count[i] == 0) { // i este prim
            for (int j = i; j <= max; j += i) {
                prime_factors_count[j]++;
            }
        }
    }
    return prime_factors_count;
}

int main() {
    ifstream inFile("divprim.in");
    ofstream outFile("divprim.out");

    int T;
    inFile >> T;

    vector<int> prime_factors_count = sieve(MAX_N);

    while (T--) {
        int N, K;
        inFile >> N >> K;

        int result = 0;
        for (int i = N; i >= 1; --i) {
            if (prime_factors_count[i] == K) {
                result = i;
                break;
            }
        }

        outFile << result << endl;
    }

    inFile.close();
    outFile.close();

    return 0;
}