#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int i,j,n,x,k,c[1000001],sol[1000001][10];
int main()
{
    f >> n;
    for(i = 2; i <= 1000000; ++i)
        if(c[i] == 0)
            for(j = i; j <= 1000000; j += i)
                ++c[j];
    for(i = 2; i <= 1000000; ++i)
    {
        for(j = 1; j <= 7; ++j)
            sol[i][j] = sol[i-1][j];
        sol[i][c[i]] = i;
    }
    for(i = 1; i <= n; ++i)
    {
        f >> x >> k;
        g << sol[x][k] << '\n';
    }
    return 0;
}