Sea ~n~ un número natural y ~M~ = {~S_1, S_2, ..., S_n~} muchas cadenas de caracteres no visibles. Deje que ~S_k~ sea una cadena de caracteres de ~M~. Entonces, cualquier carácter de ~S_k~ pertenece al conjunto {~'a'~, ~'b'~}. Tomamos nota por | ~S_k~ | el número de caracteres de la cadena ~S_k~ o su longitud equivalente. Una subsecuencia ~S_k~[~i~: ~j~] de ~S_k~ se compone de los caracteres ubicados en posiciones consecutivas ~i~, ~i + 1~, ..., ~j~. Por lo tanto, si ~S_k~ = 'abbbaababa', entonces ~S_k~[3: 6] = 'bbaa' o la subsecuencia resaltada: 'abbbaababa'.

Tarea

Dado un conjunto ~M~, se requiere determinar la longitud máxima de una subsecuencia encontrada en todas las filas de ~M~.

Entrada

En la primera línea de la entrada hay un número natural ~n~ igual al cardinal del conjunto ~M~. En cada una de las siguientes ~n~ líneas hay una cadena del conjunto ~M~.

Salida

En la primera y única línea de la salida, imprima un número natural igual a la longitud del resultado encontrado.

Restricciones y aclaraciones.

• ~1 < n < 5~

• Si ~| S | = | S1 | + | S2 | + ... + | Sn |~, entonces ~| S | < 50 001~

• Se garantiza que siempre habrá una solución.

• Garantía de que el resultado no superará los ~60~.

• Para el ~30~% de las pruebas: ~| S | < 101~

• Para el ~55~% de las pruebas: ~| S | < 3 501~

• Para el ~80~% de las pruebas: ~| S | < 10 001~

Ejemplo de Entrada

 4
 abbabaaaaabb
 aaaababab
 bbbbaaaab
 aaaaaaabaaab

Ejemplo de Salida

 5

Explicación:

La longitud de una subsecuencia de longitud máxima común es ~5~.

En el ejemplo, la subsecuencia de longitud común 5 es aaaab:

abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab.