CF1627D.Not Adding

You have an array $a_1, a_2, \dots, a_n$ consisting of $n$ distinct integers. You are allowed to perform the following operation on it:

• Choose two elements from the array $a_i$ and $a_j$ ($i \ne j$) such that $\gcd(a_i, a_j)$ is not present in the array, and add $\gcd(a_i, a_j)$ to the end of the array. Here $\gcd(x, y)$ denotes greatest common divisor (GCD) of integers $x$ and $y$.

Note that the array changes after each operation, and the subsequent operations are performed on the new array.

What is the maximum number of times you can perform the operation on the array?

你有一个由 $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$ 的最大公约数（GCD）。

注意：每次操作后数组都会发生变化，后续操作均在更新后的数组上进行。

你最多能对该数组执行多少次该操作？

The first line consists of a single integer $n$ ($2 \le n \le 10^6$).

The second line consists of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^6$). All $a_i$ are distinct.

第一行包含一个整数 $n$（$2 \le n \le 10^6$）。

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

Output a single line containing one integer — the maximum number of times the operation can be performed on the given array.

输出一行，包含一个整数——对给定数组最多可执行该操作的次数。

In the first example, one of the ways to perform maximum number of operations on the array is:

• Pick $i = 1, j= 5$ and add $\gcd(a_1, a_5) = \gcd(4, 30) = 2$ to the array.
• Pick $i = 2, j= 4$ and add $\gcd(a_2, a_4) = \gcd(20, 25) = 5$ to the array.
• Pick $i = 2, j= 5$ and add $\gcd(a_2, a_5) = \gcd(20, 30) = 10$ to the array.

It can be proved that there is no way to perform more than $3$ operations on the original array.

In the second example one can add $3$, then $1$, then $5$, and $2$.

在第一个例子中，对数组执行最多次数操作的一种方法是：

• 选取 $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$。