#include<iostream>

#include<cstdio>

using namespace std;

const int MAXN =  + ;

const int MAXM =  + ;

int n,m,l,r;

int a[MAXM],vis[MAXM];

inline int rd() {

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)) {f=(ch=='-')?-:;ch=getchar();}

    while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void find_prime() {

    a[] = ;

    vis[] = true;

    for(int i = ;i <= m;i++) {

        if(!vis[i]) {

            a[i] = a[i-] + ;

            for(int j = i+i;j <= m;j = j+i) vis[j]=true;

        } else a[i] = a[i-];

    }

    return;

}

int main() {

    scanf("%d%d",&n,&m);

    find_prime();

    while(n--) {

        l = rd(), r = rd();

        if(l <  || m < r) {

            puts("Crossing the line");

            continue;

        }

        printf("%d\n",a[r]-a[l-]);

    }

    return ;

}