#include <bits/stdc++.h>
using namespace std;
int n, m, l, r, ans, a[1000001], cnt = 1;
bool vis[1000001];
void init(){
	for(int i = 2; i <= n; i++){
		if(!vis[i]){
			a[cnt] = i;
			cnt++;
		}
		for(int j = 1; j < cnt; j++){
			if(1ll * i * a[j] > n){
				break;
			}
			vis[i * a[j]] = true;
			if(i % a[j] == 0){
				break;
			}
		}
	}
}
int main(){
	cin >> m >> n;
	init();
//	cout << a[1] << endl;
	for(int i = 0; i < m; i++){
		cin >> l >> r;
		if(l < 1 || r > n){
			cout << "Crossing the line" << endl;
		}
		else{
			ans = 0;
			for(int j = 1; a[j] <= r; j++){
				if(a[j] >= l){
					ans++;
				}
			}
			cout << ans << endl;
		}
	}
}