#include <cstdio>

using namespace std;

int t, n, k, nr_div_prim[1000010], sol[1000010][9];
long long i, j;
int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    scanf("%d", &t);

    for(i=2; i<=1000000; ++i)
        if(!nr_div_prim[i])
        {
            ++nr_div_prim[i];

            for(j=2*i; j<=1000000; j+=i)
                ++nr_div_prim[j];

        }

    for(i=2; i<=100000; ++i)
    {
        for(j=0; j<=8; ++j)
            sol[i][j] = sol[i-1][j];
        sol[i][nr_div_prim[i]] = i;
    }

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

    return 0;
}