Un jardín se puede representar como una matriz bidimensional de tamaño ~N \times N~. En cada casilla crece una flor de una especie determinada. Las posibles especies de flores corresponden a las letras A-Z, pero no todas las especies necesariamente aparecen en el jardín.

Se quiere cercar un área rectangular del jardín. Es necesario que el área contenga al menos una flor de cada especie que aparece en todo el jardín.

¿Cuántas posibles áreas cercadas existen?

Entrada

La primera línea de la entrada contiene un entero ~N~ ~-~ la longitud del lado del jardín.

Las siguientes ~N~ líneas contienen una cadena de longitud ~N~, compuesta por los caracteres A-Z ~-~ la especie de cada flor.

Salida

La salida debe contener un entero ~-~ el número de posibles áreas cercadas.

Restricciones

• ~1 \le N \le 500~

Subtareas

Subtarea	Restricciones Adicionales	Puntos	Dependencias
~1~	~N \le 10~	~4~	~-~
~2~	~N \le 20~	~6~	~1~
~3~	~N \le 50~	~10~	~1-2~
~4~	~N \le 100~	~13~	~1-3~
~5~	~N \le 200~	~25~	~1-4~
~6~	~-~	~42~	~1-5~

Ejemplos

Entrada 1

4
AAAK
ABAA
ABAA
AAAA

Salida 1

6

En la siguiente figura, las áreas rectangulares válidas están marcadas en rojo: