Counting Single-Letter Triangles

Time limit2sMemory limit128 MB

Summary

Count all size-2-or-larger right isosceles and diamond-shaped isosceles triangles made of one repeated letter, in any rotation, inside an N x N grid.

Level: Medium7 of 10
Topics: Dynamic programming, Matrix, Geometry, Implementation
Solved: No attempts yet

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.

Examples1

Example 1
Input
```
3
AAB
ABB
BBB
```
Expected output
```
10
```