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

const int N = 1e6;
int n, m, l, r;
int sum;
bool vis[N+10];

void isp() {
	vis[1] = true;
	for(int i = 2; i <= m; i++)
		for(int j = i*i; j <= m; j += i)
			vis[j] = true;
}

int main() {
	cin >> n >> m;
	isp();
	while(n--) {
		cin >> l >> r;
		
		if(l < 1 || r > m) cout << "Crossing the line" << endl;
		else {
			sum = 0;
			for(int i = l; i <= r; i++)
				if(vis[i] == false)
					sum++;
			cout << sum << endl;
		}
	}
	
    return 0;
}

RE 7个