///Nume : Purece Victor
///Scoala : C.N.I Grigore Moisil
///Clasa : a X-a C
///Email : [email protected]
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
bool numarPrim(int numar)
{
    if(numar == 2)
        return true;
    if(numar < 2 || numar % 2 == 0)
        return false;
    for(int d = 3 ; d <= numar/2; d+=2)
        if(numar % d == 0)
            return false;
    return true;
}
int main()
{
    int N, K, T, nr = 0,nrdiv, x;
    f >> T;
    while(nr < T)
    {
        f >> N >> K;
        x = 0;
        for(int i = N; i > 1; i--){
              nrdiv = 0;
            for(int j = N; j > 1; j--)
        {
            int ok = 0;
            if(i % j == 0 && numarPrim(j)==true)
                ok = 1;
            if(ok == 1){
                nrdiv++;
            }
        }
        if(nrdiv == K && x < i)
            {
                x = i;
            }};

        g << x << endl;
        nr++;
    }

    return 0;
}