#include <fstream>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

int i,j,n,k,t,ciur[1000005],m[15][1000005];
int main()
{
    for(i=2;i<=1000000;i++)
        if(ciur[i]==0)
        {
            ciur[i]=1;
            for(j=i*2;j<=1000000;j+=i)
                ciur[j]++;
        }
    m[0][1]=1;
    for(i=2;i<=1000000;i++)
    {
        for(j=0;j<=7;j++)
            m[j][i]=m[j][i-1];
        m[ciur[i]][i]=i;
    }
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>n>>k;
        g<<m[k][n]<<"\n";
    }
}