問題文

高橋君はスーパーエンジニアです。最近、 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 が含む誤情報の個数の最小値を求めてください。

入力例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