ETF  Euler Totient Function
English  Vietnamese 
In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.
Given an integer n (1 <= n <= 10^6). Compute the value of the totient φ.
Input
First line contains an integer T, the number of test cases. (T <= 20000)
T following lines, each contains an integer n.
Output
T lines, one for the result of each test case.
Example
Input: 5 1 2 3 4 5 Output: 1 1 2 2 4
hide comments
sssdhnam:
20230916 15:13:14
hope I could AC it in 10 times ☺ 

berlin03spoj:
20230711 12:50:04
hic AC in 5 times :(( 

shakur01:
20220909 13:05:38
AC in the first go. 

ishraaq_56789:
20210520 10:58:36
Proud to write an Euler Totient function from scratch and get an AC in the first go. 
Added by:  Race with time 
Date:  20090327 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 