#include <bits/stdc++.h>
using namespace std;
int n, m, l, r, pri[1000010], pnum[1000010], id, sum;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    pri[1] = 1;
    for(int i = 2; i <= m; i++) {
        if(!pri[i]) pnum[++id] = i;
        for(int j = 1; j <= id && i * pnum[j] <= n; j++) { 
            pri[i * pnum[j]] = 1;                          
            if(i % pnum[j] == 0) break;                    
        }
    }
    while(n--) {
        sum = 0;
        cin >> l >> r;
        if(l < 1 || r > m) {cout << "Crossing the line\n"; continue;}
        for(int i = l; i <= r; i++) if(!pri[i]) sum++;
        cout << sum << "\n";
    }
    return 0;
}