#include<bits/stdc++.h>  
#define int long long
using namespace std;

bitset<19345678> st;
int prime[19345678], f[19345678];
int n, m, l, r;

void Euler(int u){  //线性筛
	int cnt = 0;
	f[1] = 0;   //1没素数
	for(int i = 2; i <= u; i++){
		if(!st[i]){
			prime[cnt++] = i;
			f[i] = f[i - 1] + 1;  //前缀和优化(前缀和数组存结果)
		}
		else{
			f[i] = f[i - 1];   //前缀和转移
		}
		for(int j = 0; prime[j] <= u / i; j++){
			st[prime[j] * i] = true;
			if(i % prime[j] == 0) break;
		}
	}
}

signed main(){
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> m;
	Euler(m);
	while(n--){
		int res = 0;
		cin >> l >> r;
        //小于0或大于m就是越界
		if(l > m or r > m or l < 0 or r < 0){
			cout << "Crossing the line" << endl;
		}
		else{
			if(f[r] - f[l - 1] < 0) cout << "Crossing the line" << endl; //答案不会是负数
			else cout << f[r] - f[l - 1] << endl;
		}
	}
	
	
	
	return 0;
}