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