#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int an[N],bn[N];
bool add(int a){
	int ans=1;
	if(a!=1){
	    for(int i=2;i<=sqrt(a);i++)
	        if(a%i==0)
	            ans=0;
	    if(ans)
	        return true;
	    else
	        return false;
	}
	return false;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&an[i],&bn[i]);
		int ans=0,bns=0;
		if(an[i]>=1&&bn[i]<=m){
			bns=1;
			for(int j=an[i];j<=bn[i];j++)
			    if(add(j))
			        ans++;
		}
		else
		    printf("Crossing the line\n");
		if(bns)
		    printf("%d\n",ans);
	}
	return 0;
}