#include <fstream>
#include <cmath>
#define nmax 1000005

using namespace std;

ifstream in("divprim.in");
ofstream out("divprim.out");

int c[nmax], v[nmax], matprim[nmax][10];

void ciur()
{
    c[0]=c[1]=1;
    for(int i=2; i<=nmax; i++)
    {
        if(c[i]==0)
        {
            for(int j=i; j<=nmax; j+=i)
            {
                c[j]++;
            }
        }
    }
}
void construire()
{
    for(int i=2; i<=nmax; i++)
    {
        for(int j=0; j<=7; j++)
        {
            matprim[i][j]= matprim[i-1][j];
        }
        matprim[i][c[i]]=i;
    }
}

int n, nra, nrb;

int main()
{
    ciur();
    construire();
    in>>n;
    for(int i=1; i<=n; i++)
    {
        in>>nra>>nrb;
        out<<matprim[nra][nrb]<<"\n";
    }
    return 0;
}