#include <fstream>
#define maxim 1000000

using namespace std;

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

int i,j,n,x,y;
int v[maxim];
int a[8][maxim];

int main()
{
    for (i=2;i<=maxim;i++)
     {
         if (!v[i])
          for (j=i;j<=maxim;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;

       }

    f>>n;

     for (i=1;i<=n;i++)
      {
          f>>x>>y;
          g<<a[y][x]<<'\n';
      }

    f.close();
    g.close();
}