Гарний масив

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