Un șir $x_1, x_2, \dots x_N$ se numește vecoprim dacă pentru fiecare $i$ de la $1$ la $N − 1$, $x_i$ și $x_{i+1}$ sunt prime între ele.
Două numere sunt prime între ele dacă cel mai mare divizor comun al lor este $1$.

Se dă $N$ și un șir $a_1, a_2, \dots a_N$ de numere naturale nenule.
Într-o operație, poți alege un număr natural nenul $x$ și să îl inserezi oriunde în șir.

Cerință

Află numărul minim de operații ca să faci șirul $a$ să devină vecoprim.

Date de intrare

Pe prima linie a fișierului de intrare vecoprim.in se află numărul $N$. Pe a doua linie se află șirul $a_1, a_2 \dots, a_N$.

Date de ieșire

Să se afișeze în fișierul vecoprim.out numărul minim de operații ca să se facă șirul vecoprim.

Restricții și precizări

• $2 \leq N \leq 100 \ 000$
• $1 \leq a_i \leq 10^9$

Exemplu

vecoprim.in

6
2 4 7 3 6 1

vecoprim.out

2

Explicație

Putem să inserăm valoarea $3$ între numerele $2$ și $4$. După, putem insera valoarea $5$ între numerele $3$ și $6$. Șirul obținut este $2,\underline{3},4,7,3,\underline{5},6,1$ care este vecoprim (valorile subliniate sunt cele adăugate). Se poate demonstra că nu se poate obține un număr mai mic de operații.