eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Экстремум Эйлера

Экстремум Эйлера

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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