#include <fstream>

using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int v[1000001],i,j,k,l,n,x,p,d,nr,numar,y,ok;
int main()
{
    f>>n;
    v[1]=1;
    v[0]=1;
    for (i=2;i<=1000000;i++)
    {
        for (j=2;j<=1000000/i;j++)
        {
            v[i*j]=1;
        }
    }
    for (i=1;i<=n;i++)
    {
        f>>x>>k;
        y=x;
        d=2;
        nr=0;
        while (d*d<=x && y!=1)
        {
            p=0;
            while (y%d==0)
            {
                y=y/d;
                p++;
            }
            if (p>0)
            {
                nr++;
            }
            d++;
        }
        if (y>1)
        {
            nr++;
        }
        //g<<nr;
        if (nr==k)
        {
            g<<x<<'\n';
        }
        else
        {
            l=0;
            numar=1;
            while (j<k)
            {
                l++;
                if (v[l]==0)
                {
                    j++;
                    numar=numar*l;
                }
            }
            if (numar>x)
            {
                g<<0<<'\n';
            }
            else
            {
                ok=0;
                for (j=x-1;j>=1;j--)
                {
                    y=j;
                    d=2;
                    nr=0;
                    while (d*d<=j && y!=1)
                    {
                        p=0;
                        while (y%d==0)
                        {
                            y=y/d;
                            p++;
                        }
                        if (p>0)
                        {
                            nr++;
                        }
                        d++;
                    }
                    if (y>1)
                    {
                        nr++;
                    }
                    if (nr==k)
                    {
                        g<<j<<'\n';
                        ok=1;
                        break;
                    }
                }
                if (ok==0)
                {
                    g<<0<<'\n';
                }
            }
        }
    }
    return 0;
}