#include <cstdio>

int nr_div_prim (int n)
{
    int d = 2, e, nrdiv = 0;
    if (n < 2)
        return 0;
    while (d * d <= n && n > 1)
    {
        e = 0;
        while (n % d == 0)
        {
            e++;
            n = n / d;
        }
        if (e)
            nrdiv++;
        d++;
    }
    if (n > 1)
        nrdiv++;
    return nrdiv;
}

int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    int t, n, k;
    scanf("%d", &t);
    int i;
    for (i = 1; i <= t; ++i)
    {
        scanf("%d%d", &n, &k);
        while (nr_div_prim(n) != k && n > 0)
            n--;
        printf("%d\n", n);
    }
    return 0;
}