e-olymp
Yarışlar

Azerbaijan Programming Olympiad - 2nd Stage preparation

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

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

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

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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
1 10
1 20
1 5
Çıxış verilənləri #1
3
4
1