#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int v[1000005],i,j,t,w,maxi,st,dr,mij,b[8],a[8][1000000],p;

int main()
{
    for (i=2;i<=1000000;i++)
    {
        if (v[i]==0)
        {
            for (j=2;i*j<=1000000;j++) v[i*j]++;
            v[i]=1;
        }
    }
    for (i=1;v[i]<=7;i++)
    {
        b[v[i]]++;
        a[v[i]][b[v[i]]]=i;
    }
    fin >> t;
    for (i=1;i<=t;i++)
    {
        fin >> maxi >> w;
        st=1;
        dr=b[w];
        p=0;
        while (st<=dr)
        {
            mij=(st+dr)/2;
            if (a[w][mij]>maxi) dr=mij-1;
            else
            {
                p=mij;
                st=mij+1;

            }
        }
        fout << a[w][p] << "\n";
    }

    return 0;
}