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(S_1, S_2), MCD(S_2, S_3), ..., MCD(S_N, S_1)~

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

Escriba un programa que:

• lea desde la entrada estándar 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 hacia salida estándar el valor correspondiente al número de veces ó ~-1~ en caso contrario.

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

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 \le i \le N~