#include <stdio.h>

#define NMAX 1<<17

char ciur[NMAX];
int n,nr,q,a,b,S[NMAX];

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