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

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

Примеры