#include<fstream>
#define maxn 1000003

using namespace std;

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

int a[maxn],i,j,n,k,t,sol[maxn][8];

int main()
{
    n=1000000;

    for(i=2;i<=n;++i)
        if(!a[i])
            for(j=i;j<=n;j+=i)
                ++a[j];

    sol[1][0]=1;

    for(i=2;i<=n;++i)
        for(j=0;j<=7;++j)
            if(a[i]==j)
                sol[i][j]=i;
            else
                sol[i][j]=sol[i-1][j];

    f>>t;

    for(i=1;i<=t;++i)
    {
        f>>n>>k;

        g<<sol[n][k]<<"\n";
    }

    f.close();
    g.close();

    return 0;
}