#include <fstream>

using namespace std;

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

int T,i,j,n,k;
int ndp[1000001],sol[1000001][8];

int main()
{
    fin >> T;
    ndp[0] = 0;
    ndp[1] = 0;
    for (i=2; i<=1000000; i++)
        if (ndp[i] == 0)
            for (j=i; j<=1000000; j+=i)
                ndp[j]++;
    sol[1][0] = 1;
    for (i=2; i<=1000000; i++)
    {
        for (j=0; j<=7; j++)
            sol[i][j] = sol[i-1][j];
        sol[i][ndp[i]] = i;
    }
    for (;T--;)
    {
        fin >> n >> k;
        fout << sol[n][k] << "\n";
    }
    return 0;
}