C. Грустные степени
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано Q запросов формата (L, R).

Для каждого запроса необходимо посчитать количество таких x, что L ≤ x ≤ R и существуют натуральные числа a > 0, p > 1, для которых выполняется x = ap.

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

В первой строке задано число запросов Q (1 ≤ Q ≤ 105).

Следующие Q строк содержат по два числа L, R (1 ≤ L ≤ R ≤ 1018).

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

Выведите Q чисел — ответы на запросы.

Пример
Входные данные
6
1 4
9 9
5 7
12 29
137 591
1 1000000
Выходные данные
2
1
0
3
17
1111
Примечание

В первом запросе подходят числа 1 и 4.