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
sicklesplit: 2019-09-11 19:13:33

Was using long long and getting wa, Use float and then type convert to get AC

prabhat7298: 2019-09-09 05:10:04

Can be done in O(n) using linear sieve

sidharth20: 2019-08-14 07:10:46

AC in 100th go

Last edit: 2019-08-14 07:14:46
sanket17: 2019-07-08 09:04:00

By using seive in c++ i m getting TLE

Last edit: 2019-07-08 09:04:25
sid779: 2019-07-01 09:47:21

AC in one go using Euler's totient function.

fill32: 2019-06-19 10:00:09

for python, don't use sieve8 cause import numpy takes alot of time, use naive sive with max 10^4 is enough to get AC.

anmol_9557: 2019-06-18 19:23:03

AC in one go! just go cp-algorithm for implementation in case neede.

aj_254: 2019-05-13 20:40:10

after many optimization solved in python 0.10 sec ez pz lemon squezy used standard i/o and euler sieve and you definetely get ac

HARINDER SINGH: 2019-04-09 21:17:37

AC in one go in c++ but TLE in python3

scolar_fuad: 2019-03-29 17:34:28

Just AC in one shot wow just prime factorization


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