#include <fstream>

using namespace std;
ifstream f("divprim.in");
ofstream g("divprim..out");
bool ciur[1000000];

void gen_ciur(int n)
{
    ciur[0] = ciur[1] = true;
    for (int j = 4; j <= n; j += 2)
        ciur[j] = true;
    for (int i = 3; i * i <= n; i += 2)
        if (!ciur[i])
            for (int j = i * i; j <= n; j += 2 * i)
                ciur[j] = true;
}

int main()
{
    int T,n,k,i;
    f>>T;
    gen_ciur(1000000);
    while(f>>n>>k)
    {
        int p=1, copiek=k;
        i=2;
        while(copiek>0)
        {
            if(ciur[i]==0)
            {
                p=p*i;
                copiek--;
            }
            i++;
        }
        if(n<p) g<<0<<'\n';
        else
        {
            int nr=n-1,gasit=0;
            while(nr>0&&!gasit)
            {
                int nrdiv=0;
                if(ciur[nr]==0) nrdiv=1;
                else
                {
                    i=2;
                    while(i<nr)
                    {

                        if(ciur[i]==0&&nr%i==0)
                        {
                            nrdiv++;
                        }
                        i++;
                    }
                }
                if(nrdiv==k)
                {
                    gasit=1;
                }
                else nr--;
            }
            g<<nr<<'\n';
        }
    }
    return 0;
}