#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int m[1000010][10],prim[1000010],i,j,n,a,b;
int main()
{
    for (i=2; i<=1000000; ++i)
    {
        if (!prim[i])
            for (j=i; j<=1000000; j+=i)

                ++prim[j];


        for (j=1; j<=7; ++j)

            m[i][j]=m[i-1][j];

        m[i][prim[i]]=i;
    }
    f>>n;
    while (n--)

    {
        f>>a>>b;
        g<<m[a][b]<<'\n';
    }
    return 0;
}