#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
bool f[N];
long long n,m,pr[N],tot,ans; 
void euler(int n){
	for(int i=2;i<=n;i++) f[i]=true;
	for(int i=2;i<=n;i++){
		if(f[i]==true) pr[++tot]=i;
		for(int j=1;j<=tot&&i*pr[j]<=n;j++){
			f[i*pr[j]]=false;
			if(i%pr[j]==0) break;
		}
	}
}
int main(){
	cin>>n>>m;
	euler(1e6);
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		if(l<1||l>m||r<1||r>m){
			cout<<"Crossing the line"<<"\n";
		}
		else{
			for(int i=l;i<=r;i++){
				if(pr[i]) ans++;
			}
			cout<<ans<<"\n";
		}
	}
	return 0;
}