Nice Array

Limits: 4 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenik has an array \(a\) of \(n\) positive integers.

Zenik really likes it when adjacent elements are not coprime.

Help him — tell what is the maximum number of pairs of adjacent elements that are not coprime can be obtained by removing some elements from the array.

Input

The first line contains an integer \(n\) — the length of the array.

The second line contains \(n\) positive integers \(a_i\) — the elements of the array.

Output

In a single line, print an integer — the answer to the problem.

Constraints

\(1 \le n \le 10^5\),

\(1 \le a_i \le 10^9\).

Samples