Дано Q запросов формата (L, R).
Для каждого запроса необходимо посчитать количество таких x, что L ≤ x ≤ R и существуют натуральные числа a > 0, p > 1, для которых выполняется x = ap.
Выходные данные
Выведите Q чисел — ответы на запросы.
Примечание
В первом запросе подходят числа 1 и 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 4
9 9
5 7
12 29
137 591
1 1000000
|
2
1
0
3
17
1111
|