Descripción

Se tiene una secuencia ~S~ de ~N~ números enteros positivos ~S_1, S_2, S_3, S_4,..., S_N~. 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

• lea la secuencia ~S~,

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

• escriba el valor correspondiente al número de veces ó ~-1~ en caso contrario.

Entrada

Línea1: un número entero ~N~, Línea2: ~N~ números enteros positivos separados por espacios, representando la secuencia ~S~.

Salida

El salida contiene 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

Consideraciones

• ~1 \le N \le 200 000~

• ~1 \le S_i \le 1 000 para todo ~1 ≤ i ≤ N~