#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int v[1000005],a[8][1000005];
int main()
{
    int i,j,n,x,y;
    for (i=2; i<=1000005; i++)
    {
        if (!v[i])
        {
            for (j=i; j<=1000005; j+=i)
                v[j]++;
        }
        for (j=1; j<=7; j++)
            a[j][i]=a[j][i-1];
        if (v[i]<=7)
            a[v[i]][i]=i;
    }
    in>>n;
    for (i=1; i<=n; i++)
    {
        in>>x>>y;
        out<<a[y][x]<<'\n';
    }
}