#include<bits/stdc++.h>
using namespace std;
int n,m,l,r;
int sum[1000005];
bool prime[1000005];
int check(int x){
	if(prime[x])return 1;
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	memset(prime,true,sizeof(prime));
	cin>>n>>m;
	prime[0]=0;
	prime[1]=0;
	for(int i=2;i<=m;i++){
		if(prime[i]){
			for(int j=i*i;j<=m;j+=i){
				prime[j]=false;
			}
		}
	}
	for(int i=2;i<=m;i++)
		sum[i]=sum[i-1]+check(i);
	for(int i=1;i<=n;i++){
		cin>>l>>r;
		if(l<1||r>m){
			cout<<"Crossing the line\n";
			continue;
		}
		cout<<sum[r]-sum[l-1]<<"\n";
	} 
	
	return 0;
}