#include <iostream>
#include <fstream>

using namespace std;
ifstream f("densitate.in");
ofstream g("densitate.out");
int a,b,n,q,sir[500005],nr;
void ciuruire()
{
    nr=0;
    for(int i=2; i<=n; i++)
        if(!sir[i])
            for(int j=i*2;j<=n;j+=i)
                sir[j]=1;
    sir[1]=0;
    sir[2]=1;
    sir[3]=2;
    sir[4]=2;
    sir[5]=3;
    sir[6]=3;
    sir[7]=4;
    sir[8]=4;
    sir[9]=4;
    sir[10]=4;
    sir[11]=5;
    sir[12]=5;
    sir[13]=6;
    for(int i=3;i<=n;i++)
    {
        while(sir[i]!=0)
        {
            sir[i]=nr;
            i++;
        }
        nr++;
        sir[i]=nr;
    }
}
int main()
{
    f>>n>>q;
    ciuruire();
    for(int i=0; i<q; i++)
    {
        f>>a>>b;
        g<<sir[b]-sir[a-1]<<'\n';
        cout<<sir[b]-sir[a]<<'\n';
    }
    return 0;
}