Problems
Totient Extreme
Totient Extreme
Given the positive integer $n$, find the value of $H$ that is computed by the following code:
\includegraphics{https://static.e-olymp.com/content/3b/3b66e1b15da30beb62e25ebe4c86c304a93d22c4.gif}
Totient or phi function, $φ(n)$ is an arithmetic function that counts the number of positive integers less than or equal to $n$ that are relatively prime to $n$. That is, if $n$ is a positive integer, then $φ(n)$ is the number of such integers $k~(1 \le k \le n)$, for which $gcd(n, k) = 1$.
\InputFile
The first line contains the number of test cases $t~(0 < t \le 10^6)$. It is followed by $t$ lines each containing a number $n~(0 < n \le 10^4)$.
\OutputFile
For each line produce one line that contains the value of $H$ for the corresponding $n$.
Input example #1
2 3 10
Output example #1
16 1024