MN18-A. Oraliqdagi tub sonlar

q ta so‘rov: har birida [l, r] oralig‘idagi tub sonlar sonini toping. So‘rovlar ko‘p — har birini alohida tekshirish ulgurmaydi, Eratosfen elagi va prefiks yig‘indidan foydalaning.

Kirish ma’lumotlari

Birinchi qatorda q, keyin q qatorda l va r.

Chiqish ma’lumotlari

q qatorda javoblar.

Cheklovlar

1 ≤ q ≤ 2·10⁵, 1 ≤ l ≤ r ≤ 10⁶