ETF - Euler Totient Function

---

Problem statement

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 format

First line contains an integer T, the number of test cases. T following lines, each contains an integer n.

Output format

T lines, one for the result of each test case.

Constraints

The number of test cases. (T <= 20000)

Sample Input 1

5
1
2
3
4
5

Sample output 1

1
1
2
2
4

Explanation

N/A

---

• Solve
• Read editiorial

Running Your code....