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