Гарний масив

Limits: 4 sec., 256 MiB

У Зеника є масив \(a\) з \(n\) натуральних чисел.

Зенику дуже подобається, коли сусідні елементи не є взаємно простими.

Допоможіть йому — скажіть, яку максимальну кількість пар сусідніх елементів, що не є взаємно простими, можна отримати, видаливши з масиву деякі елементи.

Input

У першому рядку задано ціле число \(n\) — довжину масиву.

У другому рядку задано \(n\) натуральних чисел \(a_i\) — елементи масиву.

Output

У єдиному рядку виведіть ціле число — відповідь на задачу.

Constraints

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

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

Samples