#include <fstream>

using namespace std;

int v[1000005],sol[1000005][8];

inline void Ciur()
{
    int i,j,k,x;
    for(i=2;i<=1000000;++i)
    {
        if(!v[i])
            for(j=i;j<=1000000;j+=i)
                v[j]++;
        for(j=1;j<8;++j)
            sol[i][j]=sol[i-1][j];
        sol[i][v[i]]=i;
    }
}

int main()
{
    int N,K,T;
    Ciur();
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    fin>>T;
    while(T--)
    {
        fin>>N>>K;
        fout<<sol[N][K]<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}