#include <fstream>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
bool ciur[1005];
long long x,nr,sol,l=1,r,mid,i,j,n;
int divizoriPrimi(long long h)
{
    int cnt=0,d,dd;
    for(d=1;d*d<=h;d++)
    {
        if(h%d==0)
        {
            if(ciur[d]==0)
            {
                cnt++;
            }
            dd=h/d;
            if(dd!=d and ciur[dd]==0)
            {
                cnt++;
            }
        }
    }
    return cnt;

}
int main()
{
    ciur[1]=1;
    ciur[0]=1;
    for(i=2;i<=1000;i++)
    {
        if(ciur[i]==0)
        {
            for(j=i*i;j<=1000;j=j+i)
            {
                ciur[j]=1;
            }
        }
    }
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>nr>>x;
        l=1;
        r=nr;
        sol=0;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(mid>nr)
            {
                r=mid-1;
            }
            else
            {
                if(divizoriPrimi(mid)==x)
                {
                    sol=mid;
                }
                l=mid+1;
            }
        }
        fout<<sol<<'\n';
    }
    return 0;
}