e-olymp
Змагання

Azerbaijan Programming Olympiad - 2nd Stage preparation

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

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

Вхідні дані

Перший рядок містить кількість тестів n (n600). Кожний наступний рядок є окремим тестом та містить два числа low та high (0 < lowhigh1012).

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
1 10
1 20
1 5
Вихідні дані #1
3
4
1