#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int n,q,l,r;
int main(){
a[1]=1;
cin>>n>>q;
for(int i=2;i<=n/i;i++){
if(a[i]==0){
for(int j=i*i;j<=n;j+=i){
a[j]=1;
}
}
}
for(int i=2;i<=n;i++){
a[i]+=a[i-1];
}
while(q--){
cin>>l>>r;
cout<<r-l+1-(a[r]-a[l-1])<<endl;
}
return 0;
}