Problem Description

You are given an $n \times n$ grid. Each cell may contain an uppercase letter, or it may be empty. No letter appears twice in the grid.

You want to find three letters that lie on the same straight line, such that the line passes through the centers of the three cells containing the letters.

Please determine how many such lines there are in the grid.

Input Format

The first line contains an integer $n$, which is the side length of the grid.

The next $n$ lines each contain $n$ characters. Each character is either an uppercase letter or . (empty).

Output Format

Output one integer on a single line, representing the number of such lines in the grid.

4
...D
..C.
.B..
A... 

4

5
..T..
A....
.FE.R
....X
S.... 

3

10
....AB....
..C....D..
.E......F.
...G..H...
I........J
K........L
...M..N...
.O......P.
..Q....R..
....ST....

0

Hint

Explanation for Sample 1

Note that in the first sample, any three letters are on the same line, so the answer is equivalent to $C^{3}_{4} = 4$.

Constraints

For $100\%$ of the testdata, it is guaranteed that $3 \le n \le 100$, and no letter appears twice in the grid.

Notes

This problem is translated from COCI2006-2007 CONTEST #3 T3 TROJKE.

Translated by ChatGPT 5