Totient Extreme#4107
Given a positive integer , find the value of computed by the following code:
The Euler totient (or phi) function, , is an arithmetic function that counts the number of positive integers less than or equal to that are relatively prime to . In other words, for a positive integer , is the number of integers k~(1 \le k \le n) such that \gcd(n,k) = 1.
The first line contains the number of test cases t~(0 < t \le 10^6). It is followed by lines, each containing an integer n~(0 < n \le 10^4).
For each test case, print one line containing the value of corresponding to the given .
Example 1