#include<iostream>
using namespace std;
const int maxn=1e7+5;
int ans[maxn],a[maxn],n,m,l,r;
int main()
{  
    cin>>n>>m;
	for(int i=2;i*i<=m;i++)
	{
		if(!a[i])
		{
			for(int j=2;j<=m/i;j++)	a[i*j]=1;
		}
	}
	for(int i=2;i<=m;i++)	ans[i]=ans[i-1]+(1-a[i]);
	for(int i=1;i<=n;i++)
	{
		cin>>l>>r;
		if(l<1||r>m)	cout<<"Corssing the line"<<endl;
		else cout<<ans[r]-ans[l-1]<<endl;
	}
    return 0;
}

//我不知道错在哪里，有一个样例： //in:10 10 -6 6 1 9 -2 11 4 11 -2 10 -8 17 2 7 -2 5 2 8 -3 6 //out:Crossing the line 4 Crossing the line Crossing the line Crossing the line Crossing the line 4 Crossing the line 4 Crossing the line