#include <cstdio>

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 = 1 ; j < Y ; ++j)
            s[i][j] = s[aux][j];
        s[i][divprimi[i]] = i;
        ++i;
        ++aux;
    }
    std::freopen("divprim.in","r",stdin);
    std::freopen("divprim.out","w",stdout);
    std::scanf("%d",&aux);
    while (aux)
    {
        std::scanf("%d%d",&i,&j);
        std::printf("%d\n",s[i][j]);
        --aux;
    }
    std::fclose(stdin);
    std::fclose(stdout);
    return 0;
}