Description

Given $l, r$, find the number of primes in the interval $[l, r]$.

Input Format

The first line contains two integers, the number of queries $n$ and the maximum value of the right endpoint $m$.
Then follow $n$ lines, each with two integers $l, r$, representing one query.

Output Format

For each query, output one line. If $l, r \in [1, m]$, output the number of primes in the interval; otherwise, output Crossing the line.

2 5
1 3
2 6

2
Crossing the line

Hint

Constraints

• For $20\%$ of the testdata, $n, m \le 10$.
• For $100\%$ of the testdata, $1 \le n \le 1000$, $1 \le m \le 10^6$, $-10^9 \le l \le r \le 10^9$.

Translated by ChatGPT 5