Гарний масив

Обмеження: 4 сек., 256 МіБ

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Обмеження

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

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

Приклади