#include<bits/stdc++.h>
using namespace std;
int l,r,n,m,ans=0;
bool prime=true;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&l,&r);
		if(r>m||l<1)
        cout<<"Crossing the line"<<endl;
		else{
			if(l==1)
				for(int j=2;j<=r;j++){
					for(int k=2;k<=sqrt(j);k++){
						if(j%k==0){
							prime=false;
							break;
						}
					}
					if(prime==true)ans++;
					prime=true;
				}
			else
				for(int j=l;j<=r;j++){
					for(int k=2;k<=sqrt(j);k++){
						if(j%k==0){
							prime=false;
							break;
						}
					}
					if(prime==true)ans++;
					prime=true;
				}
			printf("%d\n",ans);
		}
	}
}