rt，记录

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[1000005];
int n,m;
ll prime[50005],cnt,L,R;
inline void init(){
	vis[1]=1;
	for(int i=2;i<=46340;++i){
		if(!vis[i])prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*prime[j]<=46340;++j){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
inline void solve(){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=cnt;++i)
		for(int j=max(2*1LL,(L+prime[i]-1)/prime[i]);j<=R/prime[i];++j)
			vis[j*prime[i]-L]=1;
	int ans=0;
	for(int i=0;i<=R-L;++i)
		if(!vis[i])
			++ans;
	cout<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(;n--;){
		memset(vis,0,sizeof(vis));
		cnt=0;
		cin>>L>>R;
		if(R>m){
			cout<<"Crossing the line\n";
			continue;
		}
		L=max(L,2*1LL);
		init();
		solve();
	}
	return 0;
}