Натуральне число називається майже простим, якщо воно не просте і має лише один простий дільник. Знайти кількість майже простих чисел у заданому інтервалі натуральних чисел.
Перший рядок містить кількість тестів n (n≤600). Кожний наступний рядок є окремим тестом та містить два числа low та high (0<low≤high≤1012).
Для кожного тесту вивести у окремому рядку кількість майже простих чисел на проміжку [low...high] включно.