#include <fstream>
using namespace std;
int contor[500001];
int i, n, j;
bool luat[500001];
int main()
{
	ifstream f("densitate.in");
	ofstream g("densitate.out");
	f>>n;
	for(i=2; i<=n; i++)
	{
		if(contor[i]==0)
			contor[i]=contor[i-1];
		if(!luat[i])
		{
			contor[i]=contor[i-1];
			contor[i]++;
			for(j=i+i; j<=n; j+=i)
				luat[j]=true;
		}
	}
	int q, a, b;
	f>>q;
	for(i=1; i<=q; i++)
	{
		f>>a>>b;
		if(luat[a] || a==1)
			g<<contor[b]-contor[a]<<"\n";
		else
			g<<contor[b]-contor[a]+1<<"\n";
	}
}