3280. 简单送分题

输入格式

第一行一个正整数 $n$ $(1 \leq n \leq 10^5)$。

接下来的一行是用空格隔开的 $n$ 个正整数，$a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^6)$。

输出格式

输出一行，表示答案。

1
8

4

2
2 4

4

3
2 4 1

4

6
1 1 1 1 1 1

1

6
666666 717171 666666 226 666666 999999

521721323

提示

以下内容引自维基百科。

在数论中，对正整数 $n$，欧拉函数 $\varphi (n)$ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目。例如：$\varphi (8)=4$，因为 $1,3,5,7$ 均和 $8$ 互质。

特例：$\varphi (1)=1$，小于等于 $1$ 的正整数中唯一和 $1$ 互质的数就是 $1$ 本身。

若 $n$ 是质数 $p$ 的 $k$ 次幂，$\varphi (n)=\varphi (p^{k})=p^{k}-p^{{k-1}}=(p-1)p^{k-1}$，因为除了 $p$ 的倍数外，其他数都跟 $n$ 互质。

欧拉函数是积性函数，即是说若 $m,n$ 互质，$\varphi (mn)=\varphi (m)\varphi (n)$。

欧拉函数的值可以用下面的公式表示：

$$\displaystyle \varphi(x) = x(1- \frac{1}{p_1})(1 - \frac{1}{p_2})(1 - \frac{1}{p_3}) \cdots (1 - \frac{1}{p_n})$$

其中 $p_1, p_2, \ldots, p_n$ 是 $x$ 的 $n$ 个质因子。

上面两个定理的证明略去，有兴趣可以自行搜索。