#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int n,i,j,x,k,nrd,m,d,ok;
int main()
{
    in>>n;
    for(i=1; i<=n; i++)
    {
        in>>x>>k;
        ok=1;
        for(j=x; j>=2 && ok; j--)
        {
            m=j;
            d=2;
            nrd=0;
            if(m%d==0)
            {
                nrd++;
                while(m%d==0)
                    m/=d;
                d++;
            }
            while(m>1)
            {
                if(d*d>m) d=m;
                if(m%d==0)
                {
                    nrd++;
                    while(m%d==0)
                        m/=d;
                }
                d+=2;
            }
            if(nrd==k) out<<j<<'\n',ok=0;
        }
        if(ok==1) out<<0<<'\n';
    }
}