#include <fstream>
using namespace std;
/**
NUME: Stratulat Cosmin
SCOALA: C.N.A.S.
EMAIL: [email protected]
CLASA: X (a 10-a)
**/
    ifstream f("divprim.in");
    ofstream g("divprim.out");

    int prim(int x)
    {
        int k=0;
        for(int d=3;d*d<=x;d+=2){
            if(x%d==0)
            k++;
            while(x%d==0)
                x=x/d;

        }

        return k;

    }


int main()
{
    int T, N, K;

    f>>T;


    for(int i=0;i<T;i++){
        f>>N;
        f>>K;

            for(int X=N;X>1;X--){
                    if(prim(X)==K){
                g<<X<<endl;
                X=0;}



            }

    }


    return 0;
}