#include <bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t, n, k;
int nrd[1000002], mat[1000002][8], vf[8];
void ciur()
{
    int i, j;
    for(i=2; i<=1000000; i++)
        if(!nrd[i])
            {
                for(j=i; j<=1000000; j+=i)
                    nrd[j]++;
                mat[++vf[1]][1]=i;
            }
        else
        {
            if(nrd[i]<=7)
                mat[++vf[nrd[i]]][nrd[i]]=i;
        }
}
int main()
{
    int i, st, dr, mijl, sol;
    bool ok;
    ciur();
    fin>>t;
    for(i=1; i<=t; i++)
    {
        ok=0;
        fin>>n>>k;
        if(k==0)
        {
            fout<<1<<'\n';
            ok=1;
        }
        else
        {
            sol=-1, st=1, dr=vf[k];
            while(st<=dr)
            {
                mijl=(st+dr)>>1;
                if(mat[mijl][k]<=n)
                    {
                        sol=mat[mijl][k];
                        st=mijl+1;
                    }
                else
                    dr=mijl-1;
            }
            if(sol>0)
            {
                fout<<sol<<'\n';
                ok=1;
            }
        }
        if(!ok)
            fout<<0<<'\n';
    }
    return 0;
}