eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Майже прості числа

Майже прості числа

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Натуральне число називається майже простим, якщо воно не просте і має лише один простий дільник. Знайти кількість майже простих чисел у заданому інтервалі натуральних чисел.

Вхідні дані

Перший рядок містить кількість тестів n~(n \le 600). Кожний наступний рядок є окремим тестом та містить два числа low та high~(0 < low \le high \le 10^{12}).

Вихідні дані

Для кожного тесту вивести у окремому рядку кількість майже простих чисел на проміжку [low ... high] включно.

Приклад

Вхідні дані #1
3
1 10
1 20
1 5
Вихідні дані #1
3
4
1