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

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

Вхідні дані

Перший рядок містить кількість тестів $n(n\le 600)$. Кожний наступний рядок є окремим тестом та містить два числа $low$ та $high(0<low\le high\le 10^{12})$.

Вихідні дані

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

Приклади