#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;
typedef long long ll;
int main(){
	while(1){
		system("start cmd");
	}
}

#include<bits/stdc++.h>

#define ll long long

#define un unsigned

#define int long long

#define db double

#define st string

#define ct const

#define xh(a,b,c) for(int a=b;a<=c;a++)

#define wx while(1)

#define dn(a,b,c) for(int a=b;a>=c;a--)

using namespace std;

ll n;

int f[50000010];

bool a[50000010];

ll x,y;

ll m;

signed main(){

cin>>n;

a[1]=1;

for(ll i=2;i*i<=n;i++)

if(!a[i])for(ll j=i;j<=n/i;j++)a[i*j]=1;

for(ll i=1;i<=n;i++)f[i]=f[i-1]+!a[i];

cin>>m;

for(ll i=1;i<=m;i++){

cin>>x>>y;

cout<<f[y]-f[x-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;
}