Задачі
Майже прості числа
Майже прості числа
Натуральне число називається майже простим, якщо воно не просте і має лише один простий дільник. Знайти кількість майже простих чисел у заданому інтервалі натуральних чисел.
Вхідні дані
Перший рядок містить кількість тестів 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