共振频率 (iteration)

题目描述

实验室记录了 $n$ 个正整数频率 $a_i$。研究员可以反复进行如下操作：

任意选择当前记录中已有的两个数 $a_x$ 和 $a_y$，计算 $p=\gcd(a_x,a_y)$。如果 $p$ 尚未出现在记录中，就把 $p$ 加入记录末尾。

在操作次数不限的情况下，请问最多还能向记录中加入多少个不同的数字？

输入格式

在文件 iteration.in 中读入。

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

第二行输入 $n$ 个正整数，表示数组 $a_i$。

输出格式

在文件 iteration.out 中输出。

输出一个整数，表示最多还能加入多少个数字。

样例

样例输入 #1

3
6 10 15

样例输出 #1

4

样例 1 解释

一种可行的加入过程如下：

一共可以加入 $4$ 个数字。

数据范围

对于 $20\%$ 的数据，$2\le n\le 10^2$，$1\le a_i\le 10^3$。

对于 $100\%$ 的数据，$2\le n\le 10^6$，$1\le a_i\le 10^6$。