#include<stdio.h>
int n,x,d,i,j,q,a,b,s;
int v[500001];
int main(){
	FILE * f = fopen("densistate.in","r");
	fscanf(f,"%d %d",&n,&q);
	v[1]=v[0]=0;
	for(i=2;i<=n;i++){
		if(v[i]==0){
			x++;
			v[i]=v[i-1]+1;
			for(j=i+i;j<=n;j+=i)
				v[j]=1;
		}
		else
			v[i]=v[i-1];
	}
	FILE * g = fopen("densitate.out","w");
	for(i=1;i<=q;i++){
		fscanf(f,"%d %d",&a,&b);
		s=v[b]-v[a-1];
		fprintf(g,"%d\n",s);
	}
	
	fclose(f);
	fclose(g);
	return 0;
}