给定 n 个正整数 ai,请你求出每个数的欧拉函数。
欧拉函数:对正整数N, 1∼N 中与 N 互质的数的个数被称为欧拉函数,记为 ϕ(N)。
若在算数基本定理中,N=pa1pa2…pam,则:
ϕ(N) = N×((p1−1)/p1)×((p2−1)/p2)×…×((pm−1)/pm)
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 ai。
输出共 n 行,每行输出一个正整数 ai 的欧拉函数。
3
3
6
8
2
2
4