#include <fstream>
#define NMAX 1000001
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int sol[8][NMAX], w[NMAX];
int main()
{
    int t, n, i, j, k;
    for (i=2; i<=NMAX; ++i)
        if (!w[i])
            for (j=i; j<=NMAX; j+=i)
                w[j]++;
    for (i=2; i<=NMAX; ++i)
        sol[w[i]][i]=i;
    for (i=1; i<=7; ++i)
        for (j=2; j<=NMAX; ++j)
            if (sol[i][j]==0)
                sol[i][j]=sol[i][j-1];
    in>>t;
    while (t--)
    {
        in>>n>>k;
        out<<sol[k][n]<<'\n';
    }
    return 0;
}