#include <iostream>
#include <cstring>
#include <string>

using namespace std;

#define NM 1000005

int divp[NM], best[NM][8];

int main()
{
    freopen ("divprim.in", "r", stdin);
    freopen ("divprim.out", "w", stdout);

    for (int i = 2; i <= 1000000; ++i)
        if (!divp[i]) for (int j = i; j <= 1000000; j += i) ++divp[j];

    for (int i = 1; i <= 1000000; ++i)
        for (int j = 0; j <= 7; ++j)
        {
            best[i][j] = best[i-1][j];
            if (divp[i] == j) best[i][j] = i;
        }

    int T;

    scanf ("%d", &T);

    while (T--)
    {
        int N, K;
        scanf ("%d %d", &N, &K);

        printf ("%d\n", best[N][K]);
    }

    return 0;
}