#include<bits/stdc++.h>
using namespace std;
int n,m;
int sum[10000005];
int js(int x)
{
	if(x<2)
	{
		return false;
	}
	for(int i=2; i<=sqrt(x); i++)
	{
		if(x%i==0)
		{
			return false;
		}
	}
	return true;
}
int main()
{
	cin>>n>>m;
	for(int i=1; i<=m; i++)
	{
		if(js(i))
		{
			sum[i]=sum[i-1]+1;
		}
		else
		{
			sum[i]=sum[i-1];
		}
	}
	while(n--)
	{
		int x,y;
		cin>>x>>y;
		if(y>m||x<1)
		{
			cout<<"Crossing the line\n";
			continue;
		}
		cout<<sum[y]-sum[x-1]<<endl;
	}
}