#include <bits/stdc++.h>

using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divprim.out");
# define NMAX 1000000
int t,n,k,c[NMAX+5],m[8][NMAX+5],i,j;
int bin (int n, int k)
{
    int st=1, dr=m[k][0],mij,rez=-1;
    if (m[k][1]>n) return 0;
    while (st<=dr)
        {
            mij=st+(dr-st)/2;
            if (m[k][mij]==n) return m[k][mij];
            if (m[k][mij]>n) dr=mij-1;
            else {rez=mij; st=mij+1;}
        }
    return m[k][rez];
}
int main()
{
    for (i=2;i<=NMAX;i++)
        if (c[i]==0)
            {
                for (j=i;j<=NMAX;j+=i)
                    c[j]++;
            }
    for (i=2;i<=NMAX;i++)
        {
            if (c[i]>7) continue;
            m[c[i]][0]++;
            m[c[i]][m[c[i]][0]]=i;
        }
    /*for (i=1;i<=7;i++)
        {
            for (j=1;j<=10;j++) cout<<m[i][j]<<" ";
            cout<<endl;
        }*/
    fin>>t;
    while (t--)
    {
        fin>>n>>k;
        fout<<bin(n,k)<<'\n';
    }
    return 0;
}