Гарний масив

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Обмеження

$1 \le n \le 10^5$,

$1 \le a_i \le 10^9$.

Приклади