#include<fstream>

#define NMAX 500005

using namespace std;

ifstream fin("densitate.in");
ofstream fout("densitate.out");

bool use[NMAX];
int DP[NMAX],n,q;


const int SZ=10000;
char input[SZ+1],*in;

int atoi()
{
    int nr =0;
    for(;!(*in>='0' && *in<='9') && *in;in++);
	
    if(!*in)
    {
        fin.read(input,SZ);
        in=input;
        for(;!(*in>='0' && *in<='9') && *in;in++);
    }
    for(;*in>='0' && *in<='9';in++)
    {
        nr=nr*10+(*in-'0');
        if(!*(in+1))
        {
            fin.read(input,SZ);
            in=input-1;
        }
    }
    return nr;
}


void ciur()
{
	for(int i=2;i<=n;i++)
		if(!use[i])
		{
			for(int j=i+i;j<=n;j+=i)
				use[j]=1;
			DP[i]++;
		}
}

int main()
{
	fin.read(input,SZ);
	in=input;
	n=atoi();
	q=atoi();
	ciur();
	for(int i=3;i<=n;i++)
		DP[i]+=DP[i-1];
	for(int a,b;q;q--)
	{
		a=atoi();
		b=atoi();
		fout<<DP[b]-DP[a-1]<<'\n';
	}
	
	fin.close();
	fout.close();
	
	return 0;
}