#include<iostream>
#include<cmath>
using namespace std;
int pre[1000001];
bool Find(int x){
if(x<2){
return 0;
}
for(int i=2;i<=sqrt(x);i++){
if(x%i==0){
return 0;
}
}
return 1;
}
int main(){
int q,m;
cin>>q>>m;
for(int i=1;i<=m;i++){
pre[i]=pre[i-1]+Find(i);
}
while(q--){
int l,r;
cin>>l>>r;
cout<<pre[r]-pre[l-1]<<'\n';
}
return 0;
}
