Se tiene una secuencia ~S~ de ~N~ ~(1 \leq N \leq 200 000)~ números enteros positivos S1, S2, S3, S4,..., SN ~(1 \leq S_i \leq 1000)~. Luego, cada número de la secuencia se reemplaza por el máximo común divisor (MCD) de él mismo y el siguiente número en la secuencia. El último número de la secuencia se reemplaza por el máximo común divisor de él mismo y el primero:

MCD (S1, S2), MCD (S2, S3), ..., MCD (SN, S1)

Esta operación se repite varias veces intentando que todos los números en la secuencia sean ~1~, aunque algunas veces esto no es posible.

Por ejemplo, la secuencia ~4~, ~12~, ~3~, ~9~ se tendría que reemplazar ~3~ veces:

~4~, ~3~, ~3~, ~1~

~1~, ~3~, ~1~, ~1~

~1~, ~1~, ~1~, ~1~

Tarea

• Determine si es posible cuántas veces se tiene que reemplazar la secuencia completa para obtener una secuencia formada por solamente números ~1~.

Entrada

• Línea 1: Un número entero ~N~.
• Línea 2: ~N~ números enteros positivos separados por espacios, representando la secuencia ~S~.

Salida

Un solo número entero, el número de veces que se tiene que reemplazar la secuencia completa para obtener una secuencia de solamente números ~1~. Si no es posible escriba simplemente \(–1\).

Ejemplo de Entrada

4
4 12 3 9

Ejemplo de Salida

3