rt

#include <bits/stdc++.h>
using namespace std;
#define int long long
bool vis[10000005];
void prime(int n)
{
	vis[0] = vis[1] = true;
	for(int i = 2;i * i <= n;i ++)
	{
		if(!vis[i])
		for(int j = i * i; j <= n;j += i)
		{
			vis[i] = true;
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n >> m;
	prime(m);
	for(int i = 1;i <= n;i ++)
	{
		int l,r;
		cin >> l >> r;
		if(l < 1 || r > m)
		{
			cout << "Crossing the line" << '\n';
		}
		else
		{
			int ans = 0;
			for(int i = l;i <= r;i ++)
			{
				if(vis[i])
				{
					ans++;
				}
			}
			cout << ans <<'\n';
		}
	}
}