#include<bits/stdc++.h>
using namespace std;
bitset<1000005> not_prime;
vector<int> Prime;
int n, m, l, r, f[1000005];
void p(int m){
    not_prime[1] = 1;
    for(int i = 2;i <= n;i ++){
        if(!not_prime[i])Prime.push_back(i);
        for(auto p : Prime){
            if(i * p > m)break;
            not_prime[i * p] = 1;
            if(! i % p)break;
        }
    }
    for(int i = 1;i <= m;i ++){
        if(!not_prime[i])f[i] = f[i - 1] + 1;
        else f[i] = f[i - 1];
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> m;
    p(1000000);
    for(int i = 1;i <= n;i ++){
        cin >> l >> r;
        if(l > m || r > m || l <= 0 || r <= 0){
            cout << "Crossing the line" << endl;
            continue;
        }
        cout << f[r] - f[l - 1] << endl;
    }
    return 0;
}

53, 求条！