#include<stdio.h>

using namespace std;

int main()
{
	long n,q,a,b,i,prime[50000], sol,k,j, pr[500000]={0};
	bool ok;
	FILE *f, *g;
	f = fopen("densitate.in", "r");
	g = fopen("densitate.out", "w");
	fscanf(f, "%d%d", &n,&q);
	prime[0]=2;
	k=0;
	for (i=3;i<=n;i+=2)
	{
		ok=1;
		for (j=0;j<=k;j++)
			if (i%prime[j]==0)
			{
				ok=0;
				break;
			}
		if (ok==1)
		{
			k++;
			prime[k]=i;
		}
	}
	
	for (i=0;i<=k;i++)
		pr[prime[i]] = i+2;
	
	for (i=0;i<n;i++)
		if (pr[i+1]==0)
			pr[i+1] = pr[i];
	
	
	for (i=1;i<=q;i++)
	{
		sol = 0;
		fscanf(f, "%d%d", &a,&b);
		
		sol = pr[b] - pr[a] +1;
		
		fprintf(g,"%d\n", sol);
		
	}
	return 0;
}