Почти простые числа

Натуральное число называется почти простым, если оно не простое и имеет только один простой делитель. Найти количество почти простых чисел в заданном интервале натуральных чисел.

Входные данные

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

Выходные данные

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

Примеры