T349567 欧拉函数

#### 欧拉函数的定义 > $1∼N$ 中与 $N$互质的数的个数被称为欧拉函数，记 $ϕ(N)$。 > > 若在唯一分解定理中，$N={p_1}^{\alpha_1}{p_2}^{\alpha_2}\dots{p_n}^{\alpha_n}$，则有： > > $ϕ(N)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_n})$

给定 $n$ 个正整数 $a_i$，请你求出每个数的欧拉函数。

第一行包含整数 $n$。 接下来 $n$ 行，每行包含一个正整数 $a_i$。

输出共 $n$ 行，每行输出一个正整数 $a_i$ 的欧拉函数。

#### 数据范围 $1≤n≤100$； $1≤a_i≤2×10^9$