Задачи
Экстремум Эйлера
Экстремум Эйлера
По заданному натуральному числу 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