Squirrel Liss está interesada en secuencias. Ella también tiene preferencias de números enteros. Cree que ~n~ números enteros ~a[1], a[2], ..., a[n]~ son buenos.

Ahora le interesan las buenas secuencias. Una secuencia ~x[1], x[2], ..., x[k]~ se considera buena si satisface las siguientes tres condiciones:

• La secuencia es estrictamente creciente, es decir, ~x[i] < x[i + 1]~ para cada ~i (1 \le i \le k - 1)~.
• No hay dos elementos adyacentes que sean coprimos, es decir, ~gcd(x[i], x[i + 1]) > 1~ para cada ~i (1 \le i \le k - 1)~ (donde ~gcd (p, q)~ denota el máximo común divisor de los números enteros ~p~ y ~q~) .
• Todos los elementos de la secuencia son buenos números enteros.

Calcula la longitud de la secuencia buena más larga.

Entrada

La entrada consta de dos líneas. La primera línea contiene un solo entero ~n (1 \le n \le 10^5)~ - el número de buenos enteros. La segunda línea contiene una lista separada por espacios simples de buenos enteros ~a[1], a[2], ..., a[n]~ en orden estrictamente creciente ~(1 \le a[i] \le 10^5; a[i] < a[i + 1] )~.

Salida

Imprime un solo entero: la longitud de la secuencia buena más larga.

Puntuación

• Subtarea 1 (40 ptos): ~1 \leq n \leq 50~, ~1 \leq a[i] \leq 1000~.
• Subtarea 2 (60 ptos): Sin restricciones adicionales

Ejemplos

Ejemplo 1 de entrada

5
2 3 4 6 9

Ejemplo 1 de salida

4

Ejemplo 2 de entrada

9
1 2 3 5 6 7 8 9 10

Ejemplo 2 de salida

4

Nota

En el primer ejemplo, las siguientes secuencias son ejemplos de buenas secuencias: ~[2; 4; 6; 9]~, ~[2; 4; 6]~, ~[3; 9]~, ~[6]~. La longitud de la secuencia buena más larga es ~4~.