#include <iostream>
#include <cstdio>
#include <string.h>
#include <math.h>
using namespace std;
bool pdss(int a){
	if(a<=1){
		return 0;
	}
	for(int i=2;i<sqrt(a);i++){
		if(a%i==0){
			return 0;
		}
	}
	return 1;
}
long long int n,m,l,r;
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		int g=0;
		cin>>l>>r;
		if(l<1 || r>m){
			cout<<"Crossing the line"<<endl;
		}else{
			for(int j=l;j<=r;j++){
				if(pdss(j)==1){
					g++;
				}
			}
			cout<<g<<endl;
		}
	}
	return 0;
}