Totient Extreme

Given the positive integer $n$, find the value of $H$ that is computed by the following code:

Totient or phi function, $\phi (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 $\phi (n)$ is the number of such integers $k(1\le k\le n)$, for which $gcd(n,k)=1$.

Input

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

Output

For each line produce one line that contains the value of $H$ for the corresponding $n$.

Examples