#include <fstream>

const unsigned int X(1000001);
const unsigned char Y(8);
unsigned int divprimi[X], s[X][Y];

int main (void)
{
    unsigned int i(2),j;
    while (i < X)
    {
        if (!divprimi[i])
            for (j = i ; j < X ; j += i)
                ++divprimi[j];
        ++i;
    }
    unsigned int aux;
    for (i = 2 ; i < X ; ++i)
    {
        aux = i - 1;
        for (j = 1 ; j < Y ; ++j)
            s[i][j] = s[aux][j];
        s[i][divprimi[i]] = i;
    }
    std::ifstream input("divprim.in");
    std::ofstream output("divprim.out");
    input >> aux;
    while (aux)
    {
        input >> i >> j;
        output << s[i][j] << std::endl;
        --aux;
    }
    input.close();
    output.close();
    return 0;
}