Дано 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 чисел — ответы на запросы.
В первом запросе подходят числа 1 и 4.
6 1 4 9 9 5 7 12 29 137 591 1 1000000
2 1 0 3 17 1111
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач