CF1627D Not Adding

给定一个由 $n$ 个互不相同的整数构成的数组 $a_1, a_2, \dots, a_n$。你可以对其进行如下操作： - 从数组中选择两个元素 $a_i$ 和 $a_j$（$i \ne j$），如果 $\gcd(a_i, a_j)$ 不在数组中，则将 $\gcd(a_i, a_j)$ 添加到数组末尾。这里 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。 注意，每次操作后数组都会发生变化，后续操作均在新数组上进行。 你最多可以对该数组进行多少次上述操作？

第一行包含一个整数 $n$（$2 \le n \le 10^6$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$）。所有 $a_i$ 互不相同。

输出一个整数，表示最多可以对给定数组进行多少次操作。

在第一个样例中，一种进行最多操作的方法如下： - 选择 $i = 1, j = 5$，将 $\gcd(a_1, a_5) = \gcd(4, 30) = 2$ 添加到数组中。 - 选择 $i = 2, j = 4$，将 $\gcd(a_2, a_4) = \gcd(20, 25) = 5$ 添加到数组中。 - 选择 $i = 2, j = 5$，将 $\gcd(a_2, a_5) = \gcd(20, 30) = 10$ 添加到数组中。 可以证明，原数组最多只能进行 $3$ 次操作。 在第二个样例中，可以依次添加 $3$，然后 $1$，再是 $5$，最后是 $2$。 由 ChatGPT 4.1 翻译