#include <fstream>
#define maxim 1000000

using namespace std;

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

int nr,nrr,i,j,n,nrd,x[maxim/10],y[maxim/10],nrmax;
int v[maxim+1],di[maxim/10];
int a[10][maxim];

int main()
{
    f>>n;

    for (i=1;i<=n;i++)
     {
         f>>x[i]>>y[i];
         if (x[i]>nrmax)
          nrmax=x[i];
     }

   f.close();

    for (i=2;i*i<=maxim;i++)
     if (v[i]==0)
      for (j=i*i;j<=maxim;j+=i)
       v[j]=1;

    for (i=2;i<=maxim;i++)
      if (!v[i])
       di[++nr]=i;

     for (i=1;i<=nrmax;i++)
      {
          nrr=0;

          for (j=1;di[j]<=i;j++ && j<=nr)
           if (i%di[j]==0)
            nrr++;

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

          if  (nrr<=7)
           a[nrr][i]=i;
      }

      ifstream f("divprim.in");

      f>>n;

      for (i=1;i<=n;i++)
       {
           f>>nr>>nrd;

           g<<a[nrd][nr]<<'\n';

       }

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