#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
const int N=1000002;
int t,i,n,d,v[8][N],ciur[N];
void erat()
{
    for(int i=2; i<=N; i++)
        if(ciur[i]==0)
            for(int j=i; j<=N/i; j+=i)
                ciur[j]++;
}

void form()
{
    for(int i=2; i<=N; i++)
        v[ciur[i]][i]=i;
    for(int i=1; i<=7; i++)
        for(int j=2; j<=N; j++)
            if(v[i][j]==0) v[i][j]=v[i][j-1];
}


int main()
{
    in>>t;
    erat();
    form();
    while(t)
    {
        in>>n>>d;
        out<<v[d][n]<<'\n';
        t--;
    }
}