本题需要文件读写

文件 IO 为：输入文件 gcdset.in，输出文件 gcdset.out。请使用上述文件名读入和输出。

问题描述

初始保存了 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。你可以反复利用当前已有的数字生成新数字：

任选当前已有的两个数 $a_x,a_y$，计算 $p=\gcd(a_x,a_y)$，即两数的最大公约数。如果 $p$ 尚未出现，就将它加入集合。新加入的数字也可以用于后续操作。

操作次数不限，请计算最多还能向集合中加入多少个不同的整数。初始已有的整数不计入答案。

输入格式

从文件 gcdset.in 中读入数据。

第一行输入一个整数 $n$，表示初始数字个数。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出到文件 gcdset.out 中。

输出一行一个整数，表示最多还能加入的不同整数数量。

样例输入 1

3
6 10 15

样例输出 1

4

评测数据规模

• 对于 $20\%$ 的数据，$2\le n\le10^2$，$1\le a_i\le10^3$；
• 对于所有数据，$2\le n\le10^6$，$1\le a_i\le10^6$；
• 输入均为整数。