Counting Single-Letter Triangles

Inside a text block, a filled triangle pattern may be formed by one repeated letter. Count two kinds of patterns.

The first kind is a right isosceles triangle as in (a). Its two perpendicular sides have the same length along row and column directions, and the shape may be rotated or reflected.

A          BBBAA         BB AAA        B  

(a)

The second kind is an isosceles triangle as in (b). Its apex may point up, down, left, or right.

                B  A            BB AAA          BBBAAAAA          BB                B

(b)

A side length must be at least 2. A shape consisting of just one character cell is not counted.

Given the square text block, count all single-letter triangles that satisfy these conditions.

The first line contains an integer N (1 ≤ N ≤ 500), the size of the square text block. Each of the next N lines contains a string of N uppercase English letters.

Print the total number of triangles.