您有一个数组 $$$a_1, a_2, \dots, a_n$$$ 由 $$$n$$$ 不同的整数组成。您可以对其进行以下操作:
- 从数组 $$$a_i$$$ 和 $$$a_j$$$ ($$$i \ne j$$$) 中选择两个元素,使得 $$$\gcd(a_i, a_j)$$$ 不存在于数组中,并将 $$$\gcd(a_i, a_j)$$$ 添加到数组末尾。这里 $$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。
请注意,每次操作后数组都会发生变化,后续操作都会在新数组上执行。
对数组执行操作的最大次数是多少?
输入
第一行由单个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) 组成。
第二行由 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) 组成。所有 $$$a_i$$$ 都是不同的。
输出
输出包含一个整数的单行 — 可以对给定数组执行操作的最大次数。
示例
输入 #1
5 4 20 1 25 30
输出 #1
3
输入 #2
3 6 10 15
输出 #2
4
注意
在第一个示例中,对数组执行最大次数操作的方法之一是:
- 选择 $$$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$$$。