///Ichim Vlad
///Colegiul National "Andrei Saguna"
///Clasa a X-a
///[email protected]
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int main()
{
    long long i,k,cnt,n,d,t,f,z;
    fin>>t;
    for (i=1;i<=t;i++)
    {
    fin>>n>>k;
    while(n)
    {
        cnt=0;
        for (f=1;f<=n;f++){

                if (n%f==0){
            int ok=1;
        ///----------------verif prim
        if (f<2|| f>2 && f%2==0)ok=0;
        for (d=3;d*d<=f;d+=2){if(f%d==0)ok=0;}
        if (ok==1)cnt++;
        ///---------------
    }
    }
        if (cnt==k)
            {fout<<n<<"\n"; break;}

        n--;
        if (n==0) {fout<<0<<"\n"; break;}
    }

    }
    return 0;
}