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
dennislo: 2018-06-13 05:48:33

For Java: compute + memoize totient values as you are creating the prime sieve

s_a_k_s_h_a_m: 2018-06-11 09:43:24

ans*=(1-1.0/i) will give you WA
use ans=(ans-ans/i)

aadichai22: 2018-06-02 16:04:36

Ac in one go..!

prakharvk: 2018-05-22 13:29:43

Very basic question, can be done with basic knowledge of totient function.

ramini1996: 2018-02-06 14:06:22

Use long long !!!

vishesh_345: 2017-12-28 12:00:34

It is better to find smallest prime factor and then rest of distinct factors compared to precomputing all the distinct prime factors. Second one would result into TLE.

spandana09: 2017-12-11 18:33:43

ac in one go:)

Ravi Upadhyay: 2017-11-20 10:07:00

if you are using euler totient formula then make sure to divide by p before multiplying by p-1, or else use long long int to avoid overflow.

ameyanator: 2017-11-18 21:00:12

AC with 0.01 secs in C++ using fast i/o. Time Complexity of my solution is T*sqrt(N). Fun problem but would need to read a bit on the totient function and some knowledge of how to work with prime numbers :)

jayharsh: 2017-08-12 14:59:14

AC in One Go ! 0.03 Sec........


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