#include<stdio.h>
long p[500005];
long s[500005];
long n,q,a,b,i;
void ciur(long MAXX)
{ 
  long i,j;
  p[0]=0;
  p[1]=0;
  for(i=2;i<MAXX;i++)
   p[i]=1;
  for(i=2;i<MAXX;i++) 
  { 
    if(p[i]==0)
       continue; 
    for(j=2*i;j<MAXX;j+=i) 
       p[j]=0;
   } 
}

int main()
{
 freopen("densitate.in","r",stdin);
 freopen("densitate.out","w",stdout);
 scanf("%ld%ld",&n,&q);
 ciur(n);
 for(i=1;i<=n;++i)
    if(p[i])s[i]=s[i-1]+1;
       else s[i]=s[i-1];
 for(i=1;i<=q;++i)
    {scanf("%ld%ld",&a,&b);
     printf("%ld\n",s[b]-s[a-1]);
    }
 return 0;
}