問題文

高橋君はスーパーエンジニアです。最近、 $2$ つの正の整数の最大公約数を教えてくれるロボット「ユークリッド君」を発明しました。

高橋君はユークリッド君の性能をテストするために、$N$個の正の整数からなる整数列 $A$ (1-indexed)を用意しました。

ユークリッド君には $A_i$ と $A_{i+1}$ の最大公約数を $1 ≦ i ≦ N$ について求めてもらいます。ただし $A_{N+1} = A_1$ とします。

ユークリッド君は $A_i$ と $A_{i+1}$ の最大公約数が $B_i$ だと報告してくれました。

高橋君は $B$ に幾つか矛盾があるように見えたので整数列 $A$ を元にして添削しようと思いました。しかし、あいにく整数列 $A$ のデータをなくしてしまいました。

これではユークリッド君の性能を正しく測ることができません。

しかしながら、スーパーエンジニアである高橋くんが作ったユークリッド君が間違った結果を多く報告するとは考えられません。

そこで、高橋君は $B$ に含まれている誤情報の個数として考えられる値の中で最も小さいものを、計測結果とすることにしました。

$B$ が含む誤情報の個数の最小値を求めてください。

入力

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

$N$ $B_1$ $B_2$ $B_3$ : $B_N$

• $1$ 行目には $A$ の要素数 $N (1 ≦ N ≦ 10^5)$ が与えられる。
• $2$ 行目からの $N$ 行のうち $i$ 行目には $B_i (1 ≦ B_i ≦ 10^9)$ が与えられる。

出力

ユークリッド君の報告した誤情報の個数の最小値を $1$ 行に出力せよ。 出力の最後には改行を入れること。

入力例1

3
4
2
4

出力例1

1

$B_1, B_3$が正しいとすると、$A_2$ も $A_3$ も $4$ の倍数なので $B_2 ≧ 4$ になり矛盾します。 $B_2$ が誤情報だとすると、矛盾がなくなりますので答えは $1$ です。

入力例2

10
3
1
4
1
5
9
2
6
5
3

出力例2

1

$B_8$を取り除くと矛盾がなくなります。 考えられる$A$の一例は \[21, 39, 44, 28, 65, 45, 18, 34, 25, 15\] です。

入力例3

10
2
7
1
8
2
8
1
8
2
8

出力例3

2