e-olymp
Соревнования

Azerbaijan Programming Olympiad - 2nd Stage preparation

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

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

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

Первая строка содержит количество тестов n (n600). Каждая следующая строка является отдельным тестом и содержит два числа low и high (0 < lowhigh1012).

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
3
1 10
1 20
1 5
Выходные данные #1
3
4
1