题目描述

黑板上写着 $N$ 个整数 $A_1, A_2, A_3, \\dots, A_N$。
你将进行以下操作 $N - 1$ 次：

• 选择黑板上写着的两个数并擦除它们。设擦除的两个数为 $x$ 和 $y$，则在黑板上写下 $\\gcd(x, y)$ 或者 $\\min(x, y)$。

经过 $N - 1$ 次操作后，黑板上最后留下一个整数。这个整数有多少种可能的取值？

约束条件

• $2 \le N \le 2000$
• $1 \le A_i \le 10^9$
• 输入中的所有值均为整数。

输入

从标准输入读入数据，输入格式如下：

$N$ $A_1$ $A_2$ $A_3$ $\\dots$ $A_N$

输出

打印出黑板上最后剩下的整数可能的取值数量。

示例输入 1

3
6 9 12

示例输出 1

2

最后剩下的整数可能取值为 $3$ 和 $6$。
例如，按照以下步骤操作可以使得最后留下 $3$：

• 选择 $9, 12$ 并擦除它们，在黑板上写下 $\\gcd(9, 12) = 3$；
• 选择 $6, 3$ 并擦除它们，在黑板上写下 $\\min(6, 3) = 3$。

同样地，按照以下步骤操作可以使得最后留下 $6$：

• 选择 $6, 12$ 并擦除它们，在黑板上写下 $\\gcd(6, 12) = 6$；
• 选择 $6, 9$ 并擦除它们，在黑板上写下 $\\min(6, 9) = 6$。

示例输入 2

4
8 2 12 6

示例输出 2

1

只有 $2$ 可能留在黑板上。

示例输入 3

7
30 28 33 49 27 37 48

示例输出 3

7

$1$, $2$, $3$, $4$, $6$, $7$, 和 $27$ 都可能留在黑板上。