#include<fstream>
#define nmax 1000000

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");


int n,m,k,i,j,p,x,y,nr[1000005],t,d[8][1000005];

void primus()
{
int i,j;
for(i=2;i<=nmax;i++)
    {if(nr[i]==0)
{for(j=i;j<=nmax;j=j+i)nr[j]++;}}for(i=1;i<=nmax;i++)
    {
        d[nr[i]][i]=i;}
    for(i=1;i<=7;i++)
    {
        for(j=1;j<=nmax;j++)
        {d[i][j]=max(d[i][j],d[i][j-1]);
        }}}
int main()
{
    primus();
    fin>>t;
    for(i=1;i<=t;i++)
    {
        fin>>x>>y;
        fout<<d[y][x]<<'\n';

    }
}