D - Cadena de números

Time limit: 1 second
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

Fito está estudiando Teoría de Números y encuentra muy interesante el concepto de divisor común. Por ejemplo le sorprende que el máximo común divisor de dos números sea una combinación lineal de estos. También ha estudiado cadenas de números con divisores comunes y quiere construir una con la mayor cantidad de números posibles.

Para hacer esto Fito tiene una lista con muchos enteros y con ellos va a formar una cadena de números en orden estrictamente creciente. Para todo par de números consecutivos se debe cumplir que existe un divisor común entre ellos mayor que uno.

Input

La primera línea de la entrada es un entero $N (1 ≤ N ≤ 10^5)$ la cantidad de números que tiene la lista de Fito. La segunda línea contiene $N$ enteros separados por un espacio en orden estrictamente creciente. Todos los números de la lista están entre $1$ y $10^5$.

Output

La salida es un entero con la longitud de la mayor cadena que puede formar Fito.

Sample test(s)

Input
4 2 4 5 6
Output
3