#include <bits/stdc++.h>
using namespace std;
long n, m, r, l;
int ans[1001];
bool zs[999998];

void ss(int x) {
	memset(zs, true, sizeof(zs));
	zs[0] = 0, zs[1] = 0;
	for (int i = 2; i * i <= x; i++) {
		if (zs[i]) {
			for (int j = 2; j <= x / i; j++)
				zs[i * j] = 0;
		}
	}
}

int main() {
	cin >> n >> m;
	if (m >= 999997)
		m = 999997;
	ss(m);
	for (int i = 1; i <= n; i++) {
		cin >> l >> r;
		if (l > m || r > m || l < 1 || r < 1)
			ans[i] = -1;
		else {
			for (int j = l; j <= r; j++) {
				if (zs[i] == 1)
					ans[i]++;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (ans[i] == -1)
			printf("Crossing the line");
		else
			printf("%d", ans[i]);
		cout << endl;
	}

	return 0;
}