1970: 欧拉函数
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
题目：欧拉函数
给定n个正整数a_i，请你求出每个数的欧拉函数。
欧拉函数的定义 1 ~ N 中与N互质的数的个数被称为欧拉函数，记为φ(N)。 若 N 分解质因数为 N = p₁^a₁ * p₂^a₂ * ... * pₘ^aₘ，则： φ(N) = N × (p₁ - 1)/p₁ × (p₂ - 1)/p₂ × ... × (pₘ - 1)/pₘ
给定n个正整数a_i，请你求出每个数的欧拉函数。
欧拉函数的定义 1 ~ N 中与N互质的数的个数被称为欧拉函数，记为φ(N)。 若 N 分解质因数为 N = p₁^a₁ * p₂^a₂ * ... * pₘ^aₘ，则： φ(N) = N × (p₁ - 1)/p₁ × (p₂ - 1)/p₂ × ... × (pₘ - 1)/pₘ
输入
第一行包含整数n。 接下来n行，每行包含一个正整数a_i。
输出
输出共n行，每行输出一个正整数a_i的欧拉函数。
样例输入 复制
3
3
6
8样例输出 复制
2
2
4提示
1 ≤ n ≤ 100,
1 ≤ a_i ≤ 2 * 10^9