Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Для каждого запроса необходимо посчитать количество таких x, что L ≤ x ≤ R и существуют натуральные числа a > 0, p > 1, для которых выполняется x = ap.
Входные данные
В первой строке задано число запросов Q(1 ≤ Q ≤ 105).
Следующие Q строк содержат по два числа L, R(1 ≤ L ≤ R ≤ 1018).