#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int ciur[1000001],n,t,k,sol[8][1000001];
void ciurul()
{
    for(int i=2;i<=1000001;i++)
        if(!ciur[i])
            for(int j=i;j<=1000001;j+=i) ciur[j]++;
}
void constr()
{
    for(int i=2;i<=1000001;i++)
        sol[ciur[i]][i]=i;
    for(int i=1;i<=7;i++)
        for(int j=2;j<=1000001;j++)
            if(!sol[i][j]) sol[i][j]=sol[i][j-1];
}
int main()
{
    f>>t;
    ciurul();
    constr();
    while(t--)
    {
        f>>n>>k;
        g<<sol[k][n]<<'\n';
    }
    return 0;
}