Задачі
Майже прості числа
Майже прості числа
Натуральне число називається майже простим, якщо воно не просте і має лише один простий дільник. Знайти кількість майже простих чисел у заданому інтервалі натуральних чисел.
\InputFile
Перший рядок містить кількість тестів $n~(n \le 600)$. Кожний наступний рядок є окремим тестом та містить два числа $low$ та $high~(0 < low \le high \le 10^{12})$.
\OutputFile
Для кожного тесту вивести у окремому рядку кількість майже простих чисел на проміжку $[low ... high]$ включно.
Вхідні дані #1
3 1 10 1 20 1 5
Вихідні дані #1
3 4 1