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

По заданому натуральному числу $n$ знайдіть значення $H$, яке визначається наступним кодом:

Функція Ейлера $\phi (n)$ або $totient(n)$ — це арифметична функція, яка дорівнює кількості натуральних чисел, менших або рівних $n$, що є взаємно простими з $n$. Тобто, якщо $n$ — натуральне число, то $\phi (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$.

Приклади