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
anant6025: 2019-02-06 21:06:14

Easy question if you know Sieve,Prime factorisation
AC in one go!

daku5768: 2019-01-07 16:20:49

my 50th finally

gokul27: 2018-12-26 10:58:14

AC in one go!
totient function!

raghav6: 2018-12-24 10:41:54

Finally AC with the sieve of Eratosthenes!

yaseenmollik: 2018-12-15 02:08:30

AC in one go using prime factorization

sea_26: 2018-11-21 09:31:42

Accepted in one go!

aj_254: 2018-10-09 19:47:08

how to get rid of tle in python 3.i m using o(sqrt(n)) algorithim

bendal: 2018-08-09 16:15:50

how do i overcome TLe in c++,i'm using inbuild gcd function.

deceptiveuser1: 2018-08-02 21:35:30

i have cross checked my answers a lot of times, still getting wrong answer, can the problem setter please check my solution out 22086785

ada107: 2018-06-20 15:16:46

I am getting tle in java but got it correct in c++, can anyone tell how to improve in java, have used fast scanner and printer but then also getting tle


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