SPOJ Problem Set (classical) 4141. Euler Totient Function Problem code: ETF

English

Vietnamese

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

---

Added by:	Race with time
Date:	2009-03-27
Time limit:	1s
Source limit:	50000B
Languages:	All except: ERL TECS JS