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