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