ETF - Euler Totient Function


Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274491/problem/D

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
kishor_e: 2020-08-11 09:40:37

read this topic
https://cp-algorithms.com/algebra/phi-function.html

auler_: 2020-07-15 15:52:51

@abhisek_1357, you need to divide it before multiplying. otherwise you will have integer overflow.

abhisek_1357: 2020-07-06 17:54:32

Can someone please share his/her approach ...and also if possible please debugg mine...
https://ideone.com/tlBoLl

kumar_anubhav: 2020-06-19 15:17:08

AC in one GO !! :)
learned lots of approach :)

coolboy7: 2020-06-09 19:53:10

nice question


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