#include <bits/stdc++.h>
#define in "divprim.in"
#define out "divprim.out"
using namespace std;
ifstream fin(in);
ofstream fout(out);

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

void ciur()
{
    int i,j;

    for (i = 2;i <= nmax;i++)
        if (nr[i] == 0)
            for(j = i;j <= nmax;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()
{
    ciur();
    fin >> t;
    for (i = 1; i <= t;i++)
    {
        fin >> x >> y;
        fout << d[y][x] << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}