closefrom

#include <cstdio>
#include <cmath>
using namespace std;
int n,m,l,r;
int ps[1000005];
bool zs(int num){
    if(num==1)return 0;
    if(num==2 || num==3)return 1;
    if(num%6!=1 && num%6!=5)return 0;
    int tmp=sqrt(num);
    for(int i=5;i<=tmp;i+=6)
        if(num%i==0 || num%(i+2)==0)return 0;
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    //前缀和预处理
    for(int i=1;i<=m;i++)
        if(zs(i))ps[i]=ps[i-1]+1;
        else ps[i]=ps[i-1];
        
    for(int i=1;i<=n;i++){
        scanf("%d%d",&l,&r);
        if(l<1||r>m){printf("Crossing the line\n");continue;}
        else{
            printf("%d\n",ps[r]-ps[l-1]);
//ps[r]-ps[l-1]表示l-r之间的素数的个数（1~r之间的素数个数- 1~x之间的素数个数） ps[l-1] 是前l-1数的素数个数 
        }
    }
    return 0;
}