#include <fstream>
#include <bitset>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
bitset <1000001> viz;
int v[1000001],i,j,t,nrdiv,best,m,nr,st,dr,pr[8][1000001];
int main()
{
    for (i=2;i<=1000000;i++)
    if (viz[i]==false)
    {
        for(j=i;j<=1000000;j+=i)
            viz[j]=true,v[j]++;
    }
    for (i=1;i<=1000000;i++)
    {
        pr[v[i]][++pr[v[i]][0]]=i;
    }
    f>>t;
    for (i=1;i<=t;i++)
    {
        f>>nr>>nrdiv;
        if (nrdiv==0) g<<1<<'\n';
        else
        {
            best=-1;
            st=1,dr=pr[nrdiv][0];
            while(st<=dr)
            {

                m=(st+dr)/2;
                if (nr>=pr[nrdiv][m]) best=m,st=m+1;
                else dr=m-1;
            }
            if (best!=-1)
                g<<pr[nrdiv][best]<<'\n';
            else g<<-1<<'\n';
        }
    }
    return 0;
}