#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int prime[1000010];
inline bool isprime(int qwq){
    if(qwq==1) return false;
    if(qwq==2||qwq==3) return true;
    if(qwq%2== 0) return false;
    for(int i=5;i<=sqrt(qwq)+1;i+=2)
    	if(qwq%i==0) return false;
    return true;
}
int main(){
    int n,m;
    n=read();m=read();
    for(int i=1;i<=m;++i){
        if(isprime(i)) prime[i]=prime[i-1]+1;
    	else prime[i]=prime[i-1];
    }
    while(n--){
        int l,r;
        l=read();r=read();
        if(r>m||l<1){puts("Crossing the line");continue;}
        printf("%d\n",prime[r]-prime[l-1]);
    }
    return 0;
}