Given the positive integer n, find the value of H that is computed by the following code:
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≤k≤n), for which gcd(n,k)=1.
The first line contains the number of test cases t (0<t≤106). It is followed by t lines each containing a number n (0<n≤104).
For each line produce one line that contains the value of H for the corresponding n.