#include <fstream>
using namespace std;

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

int v[1000005],c[8][1000005];
int i,j,n,x,y;

int main()
{
    for (i=2; i<=1000005; i++)
    {
        if (!v[i])
        {
            for (j=i; j<=1000005; j+=i)
                v[j]++;
        }

        for (j=1; j<=7; j++)
            c[j][i]=c[j][i-1];

        if (v[i]<=7)
            c[v[i]][i]=i;
    }

    in>>n;
    for (i=1; i<=n; i++)
    {
        in>>x>>y;
        out<<c[y][x]<<'\n';
    }
}