#include <fstream>

using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int nrp[1000005],Min[1000005][8];
int i,j,k,t,n,aux;
bool p[1000005];
int main()
{
    f>>t;
    for(i=2; i<=1000000; i++)
    {
        p[i]=1;
    }
    for(i=2; i<=1000000; i++)
    {
        if(p[i])
        {
            nrp[i]++;
            for(j=i+i; j<=1000000; j+=i)
            {
                p[j]=0;
                nrp[j]++;
            }
        }
    }
    for(i=1;i<=1000000;i++)
    {
        for(j=0;j<=7;j++)
        {
            if(nrp[i]==j)Min[i][j]=i;
            else Min[i][j]=Min[i-1][j];
        }
    }
    for(int i=1;i<=t;++i)
    {
        f>>n>>k;
        if(Min[n][k]==0)g<<-1<<'\n';
        else g<<Min[n][k]<<'\n';
    }
    return 0;
}