#include <bits/stdc++.h>

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

int divprim[10][1000007], t;
int a[1000007];

void Ciur()
{
    int i, j, n;
    n=1000001;
    for (i=2; i<=n; i++)
        if (a[i]==0)
            for (j=i; j<=n; j+=i)
                a[j]++;
    for (i=1; i<=n; i++)
        divprim[a[i]][i]=i;
    for (i=1; i<8; i++)
        for (j=1; j<=n; j++)
            divprim[i][j]=max(divprim[i][j], divprim[i][j-1]);
}

int main()
{
    int i, x, y;
    Ciur();
    fin >> t;
    for (i=1; i<=t; i++)
    {
        fin >> x >> y;
        fout << divprim[y][x] << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}