P1865 A % B Problem

The title is just to get you to click. In fact, this problem is quite easy.

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

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.

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`.

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