#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,aux(1);
    while (i < X)
    {
        if (!divprimi[i])
            for (j = i ; j < X ; j += i)
                ++divprimi[j];
        for (j = 0 ; j < Y ; ++j)
            s[i][j] = s[aux][j];
        s[i][divprimi[i]] = i;
        ++i;
        ++aux;
    }
    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;
}