Problem Description

Takahashi is a super engineer. Recently, he invented a robot named "Euclid-kun" that can tell the greatest common divisor (GCD) of two positive integers.

To test Euclid-kun's performance, Takahashi prepared an integer sequence \( A \) (1-indexed) consisting of \( N \) positive integers.

Euclid-kun is asked to find the GCD of \( A_i \) and \( A_{i+1} \) for \( 1 \leq i \leq N \), where \( A_{N+1} = A_1 \).

Euclid-kun reported that the GCD of \( A_i \) and \( A_{i+1} \) is \( B_i \).

Takahashi noticed that there seem to be some inconsistencies in \( B \). He intended to revise it based on the integer sequence \( A \), but unfortunately, he lost the data of the integer sequence \( A \).

This makes it impossible to accurately measure Euclid-kun's performance.

However, it is hard to believe that Euclid-kun, created by the super engineer Takahashi, would report many incorrect results.

Therefore, Takahashi decided to use the smallest possible number of misinformation contained in \( B \) as the measurement result.

Find the minimum number of misinformation contained in \( B \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( B_1 \) \( B_2 \) \( B_3 \) : \( B_N \)

• The first line contains the number of elements in \( A \), \( N \) (\( 1 \leq N \leq 10^5 \)).
• The next \( N \) lines contain \( B_i \) (\( 1 \leq B_i \leq 10^9 \)) for each \( i \).

Output Format

Output the minimum number of misinformation reported by Euclid-kun in one line. End the output with a newline.

Sample Input and Output

Sample Input #1

3
4
2
4

Sample Output #1

1

Sample Input #2

10
3
1
4
1
5
9
2
6
5
3

Sample Output #2

1

Sample Input #3

10
2
7
1
8
2
8
1
8
2
8

Sample Output #3

2

Notes/Hints

Sample Explanation 1

If \( B_1 \) and \( B_3 \) are correct, then both \( A_2 \) and \( A_3 \) must be multiples of 4, which leads to a contradiction since \( B_2 \geq 4 \). If \( B_2 \) is considered misinformation, the contradiction is resolved, so the answer is 1.

Sample Explanation 2

Removing \( B_8 \) resolves the contradictions. One possible example of \( A \) is \( [21, 39, 44, 28, 65, 45, 18, 34, 25, 15] \).

见题面 Input 部分

见题面 Output 部分