#include <cstdio>
using namespace std;

int t, n ,k;

int nr_div_prim(int x)
{
    int nr = 0;
    for (int d = 2; x != 1; d++)
    {
        if (x % d == 0)
            nr++;
        while(x % d == 0)
            x /= d;
    }
    return nr;
}

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

    scanf("%d\n", &t);

    while(t)
    {
        scanf("%d %d\n", &n, &k);
        int ok = 1;
        int i;
        for (i = n; i > 0 && ok == 1; i--)
        {
            if (nr_div_prim(i) == k)
            {
                printf("%d\n", i);
                ok = 0;
            }
        }
        if (i == 0)
            printf("%d\n", i);
        t--;
    }
    return 0;
}