#include <stdio.h>

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

static char c[NMAX];

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]++;
        }
}

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);
        while (n && c[n] != k)
            n--;
        printf("%d\n", n);
    }

    return 0;
}