ETF - Euler Totient Function

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


Added by:Race with time
Date:2009-03-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET

hide comments
2023-09-16 15:13:14
hope I could AC it in 10 times ☺
2023-07-11 12:50:04
hic AC in 5 times :((
2022-09-09 13:05:38
AC in the first go.
2021-05-20 10:58:36
Proud to write an Euler Totient function from scratch and get an AC in the first go.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.