#include <fstream>
#define MAX 1000000

using namespace std;
ofstream fout("divprim.out");
ifstream fin("divprim.in");

int t,n,k,nrdiv[MAX+5],d[8][MAX+5],nr[8];

void calculare_div()
{
    int i,j;

    for(i=2;i<=MAX;i++)
    {
        if(nrdiv[i]==0)
        {
            for(j=i;j<=MAX;j+=i)
            {
                nrdiv[j]++;
            }
        }
    }
}

void pre_val()
{
    int i,j;

    for(i=1;i<=7;i++)
    {
        for(j=1;j<=MAX;j++)
        {
            if(nrdiv[j]==i)
            {
                d[i][j]=j;
            }

            else
            {
                d[i][j]=d[i][j-1];
            }
        }
    }

    d[0][1]=1;
}

void pre_calc()
{
    int i;

    for(i=1;i<=MAX;i++)
    {
        d[nrdiv[i]][++nr[nrdiv[i]]]=i;
    }
}

int main()
{
    int i,st,dr,mij;

    calculare_div();
    //pre_val();
    pre_calc();

    fin>>t;

    /*for(i=1;i<=t;i++)
    {
        fin>>n>>k;
        fout<<d[k][n]<<'\n';
    }*/

    for(i=1;i<=t;i++)
    {
        fin>>n>>k;

        st=0;
        dr=nr[k];

        while(st<=dr)
        {
            mij=(st+dr)/2;

            if(n>d[k][mij])
            {
                st=mij+1;
            }

            else if(n<=d[k][mij])
            {
                dr=mij-1;
            }
        }

        fout<<d[k][dr]<<'\n';
    }

    return 0;
}