#include <fstream>
#define NMAX 1000001
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int sol[8][NMAX],i,j,n,k,t,w[NMAX];
int main()
{
    for(i=2; i<=NMAX; ++i)
        if(!w[i])
            for(j=i; j<=NMAX; j+=i) w[j]++;
    for(i=2; i<=NMAX; ++i)
        sol[w[i]][i]=i;
    for(i=1; i<=7; ++i)
        for(j=2; j<=NMAX; ++j)
            if(sol[i][j]==0) sol[i][j]=sol[i][j-1];
    fin>>t;
    while(t--)
    {
        fin>>n>>k;
        fout<<sol[k][n]<<"\n";
    }
    return 0;
}