#include <fstream>
using namespace std;

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

int divizori[1000001];

void Ciurul_lui_Eratostene ()
{
    for (int indice = 2 ; indice <= 1000000 ; indice++)
        if (!divizori[indice])
            for (int factor = 1 ; indice * factor <= 1000000 ; factor++)
                divizori[indice * factor]++;
}

int cautare (int limita , int numar_divizori)
{
    for (int indice = limita ; indice > 1 ; indice--)
        if (divizori[indice] == numar_divizori)
            return indice;

    return 0;
}

int main ()
{
    Ciurul_lui_Eratostene();

    int perechi;
    cin >> perechi;

    int limita , numar_divizori;
    for (int indice = 1 ; indice <= perechi ; indice++)
    {
        cin >> limita >> numar_divizori;
        cout << cautare(limita , numar_divizori) << '\n';
    }

    cout.close(); cin.close();
    return 0;
}