#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t,n,nrdivprim,aux,i,nrdp,d,fm,maxx;
int main()
{
    fin>>t;
    while(t--)
    {
        fin>>n>>nrdivprim;
        maxx=0;
        for(i=2; i<=n; ++i)
        {
            nrdp=0;
            d=2;
            aux=i;
            do{
                fm=0;
                while(aux%d==0)
                {
                    fm++;
                    aux/=d;
                }
                if(fm>0) nrdp++;
                d++;
            if(d*d>aux&&aux>1) aux=1, nrdp++;
            }while(aux>1);
            if(nrdp==nrdivprim)
                if(i>maxx)maxx=i;
        }
        fout<<maxx<<"\n";
    }
    return 0;
}