#include <fstream>
#define mili 1000001
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int mat[8][1000001],dr,st,mijl,i,j,nrdiv[1000001],test,t,n,poz,k;
bool ciur[1000001];
int main()
{
    for(i=2;i<=mili;i++)
    {
        if(ciur[i]==0)
        {
            ciur[i]=1;
            nrdiv[i]++;
            for(j=2*i;j<=mili;j+=i)
            {
                if(ciur[j]==0)
                    ciur[j]=1;
                nrdiv[j]++;
            }
        }
    }
    for(i=1;i<=mili;i++)
    {
        if(nrdiv[i]<=7)
            mat[nrdiv[i]][++mat[nrdiv[i]][0]]=i;
    }
    fin>>test;
    for(t=1;t<=test;t++)
    {
        fin>>n>>k;
        st=1,dr=mat[k][0],poz=0;
        while(st<=dr)
        {
            mijl=(st+dr)/2;
            if(mat[k][mijl]>n)
                dr=mijl-1;
            else
            {
                st=mijl+1;
                poz=mat[k][mijl];
            }

        }
        fout<<poz<<'\n';
    }
    return 0;
}