配点 : $600$ 点

問題文

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

• 黒板に書かれている数を $2$ つ選んで消す。消した数を $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$

出力

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

3
6 9 12

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

4
8 2 12 6

1

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

7
30 28 33 49 27 37 48

7

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