#include<bits/stdc++.h>
using namespace std;
long n,i,a,b,t,j,s,c[50000005];
bool f[50000005];
int main()
{
	cin>>n>>t;f[1]=1;
	for(i=2;i<=sqrt(n);i++)
		if(!f[i])
			for(j=i;j<=n/i;j++)f[i*j]=1;//找出n以内的素数
	for(i=1;i<=n;i++)
	{
		c[i]=c[i-1];
		if(!f[i])c[i]++;//前缀和
	}
	for(i=1;i<=t;i++)
	{
		cin>>a>>b;
		cout<<c[b]-c[a-1]<<endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	char ch=getchar();
	int x=0,m=1;
	while(!isdigit(ch)){
		if (ch=='-') m=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*m;
}
inline void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
bool p[50000010];
int f[50000010],n,t;
signed main()
{
	n=read(),t=read();
	p[1]=1;
	for (int i=1;i<=n;i++){
		if (p[i]==0) for (int j=2;j<=n/i;j++) p[i*j]=1;
		p[i]=!p[i];
		f[i]=f[i-1]+p[i];
	}
	while(t--){
		int l=read(),r=read();
		write(f[r]-f[l-1]);
		putchar('\n');
	}
	return 0;
}