SP4141 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$。