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$.