#include<fstream>
using namespace std;
ifstream f("divprim.in"); ofstream g("divprim.out");
const int Nmax=1000001;
int i,j,n,k,t,d,nr[Nmax],a[Nmax][9];
int main()
{   d=2;
    while(d<Nmax)
    {   for(i=d;i<Nmax;i+=d) nr[i]++;
        d++;
        while(nr[d]) d++;
    }
    for(i=1;i<=Nmax;i++) a[i][nr[i]]=i;
    for(i=1;i<=Nmax;i++)
        for(j=1;j<=7;j++)
            if(a[i-1][j]>a[i][j]) a[i][j]=a[i-1][j];
    f>>t;
    for(i=1;i<=t;i++)
    {   f>>n>>k;
        g<<a[n][k]<<'\n';
    }
    g.close(); return 0;
}