#include <fstream>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

int n, x, k;
bool v[1000005];
int nd[1000005], l;
int din[9][1000000];

void ciur()
{
    int i, j;
    for (i = 2; i <= 1000000; i++)
        if (v[i] == 0)
            for (j = 2*i; j <= 1000000; j += i)
                v[j] = 1, nd[j]++;
    for (i = 1; i <= 8; i++)
    {
        din[i][0] = 0;
        for (j = 1; j <= 1000000; j++)
            if (nd[j] == i)
                din[i][j] = j;
            else
                din[i][j] = din[i][j-1];
    }
}

int main()
{
    ciur();
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        f >> x >> k;
        g << din[k][x] << "\n";
    }
    return 0;
}