/*
Nume: Sas Vlad-Stefan
Scoala: Colegiul National "Radu Negru" Fagaras
Email: [email protected]
Clasa: a X-a
*/

#include <fstream>
#include <vector>
#include <math.h>

bool ePrim (int numar) {
    for (int i = 2; i <= sqrt(numar); i++) {
        if (numar % i == 0) return false;
    }
    return true;
}

int main() {
    std::ifstream inputFile("divprim.in");
    std::ofstream outputFile("divprim.out");

    int numarTeste;
    int numarDivizori, numarMaxim;
    bool gasit = false;
    std::vector<int> divizori;

    inputFile >> numarTeste;

    for (; numarTeste != 0; numarTeste--) {
        inputFile >> numarMaxim >> numarDivizori;

        for (int i = numarMaxim; i > 1; i--) {
            for (int ii = i-1; ii > 1; ii--) {
                if (i % ii == 0 && ePrim(ii)) divizori.push_back(ii);
            }
            if (divizori.size() == numarDivizori) {
                outputFile << i << '\n';
                divizori.clear();
                gasit = true;
                break;
            }
            divizori.clear();
        }
        if (!gasit) outputFile << 0 << '\n';

        gasit = false;
    }

    inputFile.close();
    outputFile.close();
    return 0;
}