August 18. Kiev Summer School
Given the value of n, you will have to find the value of H. The meaning of H is given in 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 integers k in the range 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 ≤
For each line produce one line that contains the value of H for the corresponding n.
2 3 10