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