#include <cstdio>

const int NMAX = 1000000;
int t, n, k, p[NMAX + 1], a[NMAX + 1][8];

void ciur()
{
    for (int i = 2; i <= NMAX; i = i + 2)
        p[i] = 1;
    for (int i = 3; i <= NMAX / 2; i = i + 2)
    {
        if (p[i] == 0)
        {
            for (int j = i + i; j <= NMAX; j = j + i)
                p[j]++;
            p[i] = 1;
        }
    }
}
int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    ciur();
    for(int i = 1; i <= NMAX; ++i)
        for(int j = 0; j <= 7; ++j)
            if(p[i] == j)
                a[i][j] = i;
            else
                a[i][j] = a[i - 1][j];
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &k);
        printf("%d\n", a[n][k]);
    }
    return 0;
}