#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 7;
int l, r, a[N], arr[N], n, m;
signed main(){
    cin >> n >> m;
    a[1] = 1;
    for(int i = 2; i * i <= m; i ++){
        if(a[i] == 0){
            for(int j = i + i; j <= m; j += i)
                a[j] = 1;
        }
    }
    for(int i = 1; i <= m; i ++){
        if(a[i] == 0) arr[i] = arr[i - 1] + 1;
        else arr[i] = arr[i - 1];
    }
    for(int i = 1; i <= n; i ++){
        cin >> l >> r;
        if(r > m) cout << "Crossing the line\n";
        else cout << arr[r] - arr[l - 1] << "\n";
    }
    return 0;
}