問題文

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

出力

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

入力例 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$ が最後に黒板に残る整数として考えられるものです。