#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];

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;
}

int main()
{
    int i;

    calculare_div();
    pre_val();

    fin>>t;

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

    return 0;
}