#include <fstream>

using namespace std;

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

int ciur[1000002],a[8][1000002];
int t,n,k;

void ciurare()
{
    for (int i=2;i<=1000000;i++)
        if (!ciur[i])
        {
            for (int j=i;j<=1000000;j+=i) ciur[j]++;
            ciur[i]=1;
        }
}

void calculare()
{
    for (int i=1;i<=7;i++)
        for (int j=1;j<=1000000;j++)
        {
            if (ciur[j]==i)a[i][j]=j;
            else a[i][j]=a[i][j-1];
        }
}

int main()
{
    ciurare(),calculare();

    fin >> t;

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

    return 0;
}