题目描述

黒板に $N$ 個の整数 $A_1,\ A_2,\ A_3,\ \dots,\ A_N$ が書かれています。
あなたは次の操作を $N\ -\ 1$ 回行います。

• 黒板に書かれている数を $2$ つ選んで消す。消した数を $x$ と $y$ として、$\gcd(x,\ y)$ と $\min(x,\ y)$ のどちらか一方を黒板に書く

$N\ -\ 1$ 回の操作を終えた後、黒板にはただ一つの整数が残りますが、この整数として考えられるものはいくつありますか ?

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

黒板に残る整数として考えられるものの個数を出力せよ。

题目大意

有 $n$ 个整数，你每次可以将其中两个数 $x,y$ 去掉，并添上 $\gcd(x,y)$ 或 $\min(x,y)$。问最后剩下的一个数有多少种可能的取值。

3
6 9 12

2

4
8 2 12 6

1

7
30 28 33 49 27 37 48

7

提示

制約

• $2\ \le\ N\ \le\ 2000$
• $1\ \le\ A_i\ \le\ 10^9$
• 入力は全て整数

Sample Explanation 1

$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$ を黒板に書く

Sample Explanation 2

$2$ が、黒板に残る数として考えられる唯一の数です。

Sample Explanation 3

$1,\ 2,\ 3,\ 4,\ 6,\ 7,\ 27$ が最後に黒板に残る整数として考えられるものです。