#include<fstream>
using namespace std;
int er(int a)
{
	int x,y,z=0;
	bool ok[50000];
	for(x=2;x<=a;++x)
		if(ok[x]==false)
			for(y=2;y<=a/x;++y)
				ok[x*y]=true;
	for(x=2;x<=a;x++)
		if(ok[x]==false)
			z++;
	return z;
}
int main()
{
	int N,Q,a,b;
	ifstream in("densitate.in");
	ofstream out("densitate.out");
	in>>N>>Q;
	for(;Q;--Q)
	{
		in>>a>>b;
		out<<er(b)-er(a-1)<<endl;
	}
	return 0;
}