#include <fstream>

using namespace std;
ifstream f("densitate.in");
ofstream g("densitate.out");
int v[500001],i,j,q,a,b,n,t;
int main()
{f>>n;
    for(i=2;i<=n;i++)
          v[i]=1;
    for(j=4;j<=n;j=j+2)
             v[j]=0;
    for(i=3;i<=n;i+=2){
     if(v[i]==1)
            for(j=3*i;j<=n;j+=2*i)
                v[j]=0;
          }
          for(i=2;i<=n;i++)
              v[i]+=v[i-1];
    f>>t;
    for(i=1;i<=t;i++){
        f>>a>>b;
        g<<v[b]-v[a-1]<<'\n';

    }
   return 0;
    }