#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
const int NMAX=1000005;
const int KMAX=10;
int V[NMAX],M[NMAX][KMAX];
int T,X,Y;
void eratostene()
{
    for (int i=2; i<=NMAX; i++)
    {
        if (V[i]==0)
        {
            for (int j=i; j<=NMAX; j+=i)
                V[j]++;
        }
        M[i][V[i]]=i;
    }
for (int j=1; j<=7; j++)
    for (int i=1; i<=NMAX; i++)
    if (M[i][j]==0)
    M[i][j]=M[i-1][j];
}
int main()
{
    eratostene();
    fin>>T;
    for (int i=1; i<=T; i++)
    {
        fin>>X>>Y;
        fout<<M[X][Y]<<"\n";
    }
    return 0;
}