Задачі
Экстремум Эйлера
Экстремум Эйлера
По заданному натуральному числу n найдите значение H, которое задается следующим кодом:
Функция Эйлера φ(n) или totient(n) является арифметической функцией, равной количеству натуральных чисел, меньших или равных n, взаимно простых с n. То есть если n натуральное число, то φ(n) равно количеству таких k~(1 \le k \le n), что НОД(n, k) = 1.
Вхідні дані
Первая строка содержит количество тестов t~(0 < t \le 10^6). Каждая из следующих t строк содержит одно число n~(0 < n \le 10^4).
Вихідні дані
Для каждого теста выведите в отдельной строке значение H для соответствующего значения n.
Приклад
Вхідні дані #1
2 3 10
Вихідні дані #1
16 1024