#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define il inline
#define re register 

il bool P(re int x){
    
    if (x < 2) return 0;
    if (x == 2) return 1;
    for (re int i = 2;i * i <= x;i++)
        if (x % i == 0)
            return 0;
    return 1;
    
}

const int MAXN = 1e6+5;

int main(){
    
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    
    re bool a[MAXN];
    re int n,m,l,r,ans = 0;
    
    cin >> n >> m;
    memset(a,0,sizeof(a));
    for (re int i = 1;i <= m;i++) a[i] = P(i);
    while (n--){
        
        ans = 0;
        cin >> l >> r;
        if (l < 1 || r > m) cout << "Crossing the line"s << endl;
        else{
            
            for (re int i = l;i <= r;i++) 
                if (a[i])
                    ans++;
            cout << ans << endl;
            
        }
        
    }
    
    return 0;
}