3280. 简单送分题

输入格式

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

接下来的一行是用空格隔开的 $n$ 个正整数，$a_1,a_2,\dots ,a_n$ $(1\le a_i\le {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$，欧拉函数 $\phi (n)$ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目。例如：$\phi (8)=4$，因为 $1,3,5,7$ 均和 $8$ 互质。

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

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

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

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

$${\displaystyle \phi (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,\dots ,p_n$ 是 $x$ 的 $n$ 个质因子。

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