ETF - Euler Totient Function

### 题目描述 在数论中，对正整数$n$，欧拉函数是小于$n$的正整数中与$n$互质的数的数目($\varphi (1)=1$)。 问题是，给定一个整数$n$,计算$\varphi (n)$的值 ### 输入格式 第一行包含一个整数$T$代表测试数据组数 接下来的$T$行每行包含一个整数$n$。 ### 输出格式 $T$行，第$i$行是数据给出的第$i$个整数$n$的欧拉函数的值$\varphi (n)$。 ### 数据范围 $1 \leq n \leq 10^6,T\leq 20000$。

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 φ.

First line contains an integer T, the number of test cases. (T <= 20000) T following lines, each contains an integer n.

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

5
1
2
3
4
5

1
1
2
2
4

5
1
2
3
4
5

1
1
2
2
4