#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int a,b;
bool pr[N];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	memset(pr,1,sizeof(pr));
	pr[1]=false;
	for(int i=2;i<=sqrt(N);i++)
	if(pr[i])
	for(int j=2;j<=N/i;j++)
	    pr[i*j]=false;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a,&b);
		int ans=0;
		if(a>=1&&b<=m){
			for(int j=a;j<=b;j++)
			    if(pr[j])
			        ans++;
			printf("%d\n",ans);
		}
		else
		    printf("Crossing the line\n");
	}
	return 0;
}