AT_abc191_f [ABC191F] GCD or MIN

[problemUrl]: https://atcoder.jp/contests/abc191/tasks/abc191_f 黒板に $ 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 $

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

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