#include <bits/stdc++.h>
#include <unordered_set>

#define x first
#define y second

using namespace std;

typedef long long ll;
const int N = 1e6 + 10;

int cnt,n,q;
int p[N],f[N];
bool st[N];

void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) p[cnt++]=i;
        for(int j=0;p[j]<=n/i;j++)
        {
            st[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
    for(int i=2;i<=n;i++)
        f[i]=f[i-1]+(st[i]^1);
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    init(N);
    cin>>q>>n;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        if(l<1||r>n)
        {
            puts("Crossing the line");
            continue;
        }
        cout<<f[r]-f[l-1]<<endl;
    }

    return 0;
}