读写要求

本题采用文件读写，请在提交代码时使用正确的文件名，否则会导致 RE。

输入文件：add.in

输出文件：add.out

题目描述

你有一个由 $n$ 个不同整数组成的数组 $a_1,a_2,\dots,a_n$。你可以对其执行以下操作：

• 从数组中选出两个元素 $a_i$ 和 $a_j$ ($i\neq 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\le a_i\le 10^6$)。所有 $a_i$ 互不相同。

输出格式

输出一行一个整数，表示最多能执行的操作次数。

样例输入

5
4 20 1 25 30

3

样例解释

一种最大化操作次数的方式为：

• 选取 $i=1,j=5$，添加 $\gcd(4,30)=2$ 到数组末尾。
• 选取 $i=2,j=4$，添加 $\gcd(20,25)=5$ 到数组末尾。
• 选取 $i=2,j=5$，添加 $\gcd(20,30)=10$ 到数组末尾。

可以证明无法执行超过 $3$ 次操作。

3
6 10 15

4

样例解释

可以依次添加 $3,1,5,2$。

数据范围

• $2\le n\le 10^6$
• $1\le a_i\le 10^6$
• 所有 $a_i$ 互不相同