ssdj

Because not everyone scored a 10 on the mock exam, the school administration decided to punish the students in an inhumane way: they were no longer allowed to go to the theater or read works by the great literary classics. Their only solace was a matrix with $N$ rows and $N$ columns containing only lowercase letters of the English alphabet, for which they had to identify the valid submatrices. A submatrix is considered valid if it simultaneously meets the following conditions:

• It has at least two rows and at least two columns.
• The letters in the top-left and bottom-right corners of the submatrix are lexicographically larger (strictly) than all other letters in the submatrix.

Task

Help the high school students find the number of valid submatrices in the matrix and thus escape the horrible punishment.

Input data

The file ssdj.in contains on the first line the natural number $N$, and on the next $N$ lines, there are $N$ lowercase letters each, not separated by spaces.

Output data

The file ssdj.out contains a single natural number representing the number of valid submatrices.

Constraints and Notes

• $1 \leq N \leq 1\ 000$
• For tests worth $10$ points, $N \leq 50$
• For tests worth $20$ points, the matrix will contain only the letters a and b

Example

ssdj.in

4 
maea
bcda
aaae
aaaa

ssdj.out

3

Explanation

The valid submatrices are:

ma
bc 

ea
da
ae

da
ae