#include <fstream>

    const unsigned int X(1000000);
    const unsigned int Y(7);
    unsigned int divprimi[X],s[X][Y];

int main (void)
{
    unsigned int aux;
    {
        const unsigned int *const LIMIT(divprimi + X);
        unsigned int *pointer(divprimi + 1);
        while (pointer < LIMIT)
        {
            if (!*pointer)
            {
                aux = pointer - divprimi;
                ++aux;
                while (pointer < LIMIT)
                {
                    ++*pointer;
                    pointer += aux;
                }
                pointer = divprimi + aux;
                continue;
            }
            ++pointer;
        }
    }
    unsigned int i(1),j;
    while (i < X)
    {
        aux = i - 1;
        for (j = 0 ; 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;
            --i;
            output << s[i][j] << std::endl;
            --aux;
        }
        input.close();
        output.close();
    }
    return 0;
}