#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
bool isprime(int k)
{
    
    if(k==1)
    {
        return 0; 
    }
    for(int i=2;i<=sqrt(k);i++)
    {
        if(k%i==0)
        {
            return 1; 
        }
    }
}
int main()
{
	int n,max,cnt=0;
	cin>>n>>max;
	int number[n+2][2];
	for(int i=1;i<=n;i++)
	{
	    cin>>number[i][1]>>number[i][2];
	}
    	/*for(int i=1;i<=n;i++)
    	{
    	    if(number[i][2]>max)
    	    {
    	        
    	    }
    	}*/
    for(int j=1;j<=n;j++)
	{
	    for(int k=number[j][1];k<=number[j][2];k++)
	    {
	        if(number[j][2]>max)
	        {
	            cout<<"Crossing the line"<<endl;
	            break;
	        }
	        else
	        {
	            if(isprime(k))
	            {
	                cnt++;
	            }
	        }
	        
	    }
	    cout<<cnt<<endl;
	    cnt=0;
	}
	
	return 0;
}