0873

873. 欧拉函数

题目

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

欧拉函数的定义

$1 \sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $ϕ(N)$。

若在算数基本定理中，$N = p_1^{a_1}p_2^{a_2}…p_m^{a_m}$，则：

$ϕ(N)$ = $N \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2} \times … \times \frac{p_m-1}{p_m}$

输入格式

第一行包含整数 $n$。

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

输出格式

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

数据范围

$1 \le n \le 100$,

$1 \le a_i \le 2 \times 10^9$

输入样例：

3
3
6
8

输出样例：

2
2
4

题解