Hide

Problem E
Trojke

Mirko and Slavko are playing a new game, “Trojke” (Triplets, in English). First they use a chalk to draw an $N \times N$ square grid on the road. Then they write letters into some of the squares. No letter is written more than once in the grid.

The game consists of trying to find three letters on a line as fast as possible. Three letters are considered to be on the same line if there is a line going through the centre of each of the three squares.

After a while it gets harder to find new triplets. Mirko and Slavko need a program that counts all the triplets, so that they know if the game is over or they need to search further.

Input

The first line contains an integer $N$ ($3 \le N \le 100$), the dimension of the grid.

Each of the $N$ following lines contains $N$ characters describing the grid – uppercase letters and the character ’.’ which marks an empty square.

Output

Output the number of triples on a single line.

Sample Input 1 Sample Output 1
4
...D
..C.
.B..
A...
4
Sample Input 2 Sample Output 2
5
..T..
A....
.FE.R
....X
S....
3
Sample Input 3 Sample Output 3
10
....AB....
..C....D..
.E......F.
...G..H...
I........J
K........L
...M..N...
.O......P.
..Q....R..
....ST....
0

Please log in to submit a solution to this problem

Log in