#include<bits/stdc++.h> 
using namespace std;
const int maxn=1e6+10;
int a[maxn],b[maxn];
int gcd(int x){
	if(x==1)return 0;
	int q=1;
	for(int i=2;i*i<=x;i++){
		if(x%i==0)q=0;
	}
	return q;
}
int main (){
	int n,m,l,r,ans=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		b[i]+=b[i-1]+gcd(i);
	}
	for(int i=1;i<=n;i++){
		cin>>l>>r;
		if(l>=1&&l<=m&&r>=1&&r<=m){
			ans=b[r]-b[l-1];
			cout<<ans<<endl;
		}else cout<<"Crossing the line"<<endl;
	}
	
	return 0;
}

67pts TLE4,5,6,7,14