#include<iostream>
#include<cstdio>
using namespace std;
int n, m;
bool vis[1000005];
int ans[1000005];
int prime[1000005];
int cnt = 0;
int main(){	
	scanf("%d%d", &n, &m);
	for(int i = 2; i <= m; i++){
		ans[i] = ans[i-1];//继承 
		if(!vis[i]){
			prime[cnt++] = i;
			ans[i] = cnt;
		}
		for(int j = 0; j < m && i * prime[j] < m; j++){
			vis[i * prime[j]] = 1;
			if(!i * prime[j])
				break;
		}
	}
	for(int i = 1; i <= n; i++){
		int l, r;
		scanf("%d%d", &l, &r);
		if(l > m || l < 1 || r > m || r < 1){
			printf("Crossing the line\n");
			continue;
		}
		printf("%d\n", ans[r] - ans[l-1]);
	}
	return 0;
}