#include <stdio.h>
#include <stdint.h>

#define IN "divprim.in"
#define OUT "divprim.out"
#define NMAX 1000001

/* sol[i][j] = n <= i a.i. n are j divizori */
static uint8_t c[NMAX];
static int sol[NMAX][8];

static void ciur(void)
{
    int i, j;

    for (i = 2; i < NMAX; i++)
        if (!c[i]) {
            c[i] = 1;
            for (j = 2; j * i < NMAX; j++)
                c[i * j]++;
        }

    for (i = 1; i < 8; i++)
        for (j = 2; j < NMAX; j++)
            if (ciur[j] == i)
                sol[j][i] = j;
            else
                sol[j][i] = sol[j - 1][i];
}

int main(void)
{
    int t, n, k;

    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);

    ciur();

    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        printf("%d\n", sol[n][k]);
    }

    return 0;
}