#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;
    {
        unsigned int *a(divprimi + 2),*b,*c(&s[1][1]),*d(&s[2][1]);
        const unsigned int *const LIMIT(divprimi + X);
        while (i < X)
        {
            j = *a;
            if (!j)
                for (b = a ; b < LIMIT ; b += i)
                    ++*b;
            *d = *c;
            ++c;
            ++d;
            *d = *c;
            ++c;
            ++d;
            *d = *c;
            ++c;
            ++d;
            *d = *c;
            ++c;
            ++d;
            *d = *c;
            ++c;
            ++d;
            *d = *c;
            ++c;
            ++d;
            *d = *c;
            c += 2;
            d += 2;
            s[i][divprimi[i]] = i;
            ++i;
            ++a;
        }
    }
    std::freopen("divprim.in","r",stdin);
    std::freopen("divprim.out","w",stdout);
    unsigned int aux;
    std::scanf("%u",&aux);
    while (aux)
    {
        std::scanf("%u%u",&i,&j);
        std::printf("%u\n",s[i][j]);
        --aux;
    }
    std::fclose(stdin);
    std::fclose(stdout);
    return 0;
}