#include <fstream>

using namespace std;

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

int f[1000005], d[8][1000005];

void ciur()
{
    for(int i = 2; i <= 1000001; ++i)
        if(!f[i])
            for(int j = i; j <= 1000001; j += i) f[j]++;
    for(int i = 1; i <= 1000001; ++i) d[f[i]][i] = i;
    for(int i = 1; i <= 7; ++i)
        for(int j = 1; j <= 1000001; ++j) d[i][j] = max(d[i][j], d[i][j - 1]);
}

int main()
{
    int t, n, k;
    ciur();
    fin >> t;
    for(int i = 1; i <= t; ++i)
    {
        fin >> n >> k;
        fout << d[k][n] << '\n';
    }
    return 0;
}