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


hide comments
sssdhnam: 2023-09-16 15:13:14

hope I could AC it in 10 times ☺

berlin03spoj: 2023-07-11 12:50:04

hic AC in 5 times :((

shakur01: 2022-09-09 13:05:38

AC in the first go.

ishraaq_56789: 2021-05-20 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: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