Counting Single-Letter Triangles

Problem

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          BBB
AA         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          BBB
AAAAA          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.

Input

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.

Output

Print the total number of triangles.