用线筛加上前缀和做的，不知道为什么有几个点一直tle

#pragma GCC optimize("O2")
#include <bits/stdc++.h>

#define mp make_pair
#define phb push_back
#define ppb pop_back
#define eb emplace_back
#define pp pop
#define ph push
#define ff first
#define ss second
#define htl(v, n) v.begin()+1,v.begin()+1+(n), greater<decltype(v[1])>()
#define lth(v, n) v.begin()+1,v.begin()+1+(n), less<decltype(v[1])>()
#define Max(a, b) ((a > b) ? a : b)
#define Min(a, b) ((a < b) ? a : b)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define rFOR(i, a, b) for(int i = (a); i >= (b); i--)
#define vFOR(it, a) for(auto it = a.begin();it != a.end();it++)
#define DEBUG(x) cout << #x << " = " << (x) << endl
#define checktime() cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n"
#define endl '\n'
#define faster_cpp_io() std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define setp(n) fixed<<setprecision(n)
#define case(t) int t;cin >> t;while(t--)

using namespace std;
using pll = pair<long,long>;
using pii = pair<int,int>;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using mll = map<ll, ll>;
using umll = unordered_map<ll, ll>;

constexpr ll mod = 1e5+7;
constexpr ll inf = 0x7fffffffffffffff;
constexpr ld pi = acos(-1);
constexpr ld eps = 1e-9;
constexpr ll cap = 1e6+5;

vl prime(cap);ll ti;
bool isprime[cap];
ll cnt[cap];

void solve(){
	int n, m;
	scanf("%d%d",&n,&m);
	FOR(i, 2, m){
		if (!isprime[i])
		{
			prime[++ti]=i;
			cnt[i] = cnt[i-1] + 1;	
		}
		else
		{
			cnt[i] = cnt[i-1];
		}
		
		FOR(j, 1, ti){
			if (i*prime[j]<=m)
			{
				isprime[i*prime[j]] = 1;
			}
			if (i%prime[j]==0)
			{
				break;
			}
		}
	}
	ll l, r;
	FOR(i, 1, n){
		scanf("%lld%lld", &l, &r);
		if (l<1 || r>m)
		{
			cout << "Crossing the line" << endl;
		}
		else
		{
			cout << cnt[r] - cnt[l-1] << endl;
		}
	}
}

int main()
{
	// faster_cpp_io();

	// case(t)
	solve();
    
   // checktime();
   // system("pause");
    return 0;
}