#include<fstream>
#include<iostream>
#include<vector>
#include <cstring>
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];
const int nmax=1000000;

void ciur()
{
    int i,j;
    //for(i=2;i<=nmax;i++) nr[i]=1;

    for(i=2;i<=nmax;i++)
    {
        if(nr[i]==0)
        {
            //fout<<"ok";
            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]);
        }
    }

    for(i=1;i<=7;i++)
    {
        for(j=1;j<=nmax;j++)
        {
            //fout<<d[i][j]<<" ";
        }
        //fout<<"\n";
    }

}



int main()
{
    ciur();
    fin>>t;
    for(i=1;i<=t;i++)
    {
        fin>>x>>y;
        fout<<d[y][x]<<"\n";

    }
}