Простые на отрезках

Дано $q$ запросов. Для каждого — пары $L$ и $R$ — выведите количество простых чисел от $L$ до $R$ включительно.

В первой строке число $q$ от $1$ до $10^5$. Во второй — $2q$ чисел: пары $L$ и $R$ подряд, $1 \le L \le R \le 2 \cdot 10^6$.

$q$ чисел через пробел.

Решето строится один раз. Дальше по нему заводятся накопленные суммы — и любой запрос становится одним вычитанием.