JMU CS280 SP18 WK10

Start

2018-03-20 20:30 CET

JMU CS280 SP18 WK10

End

2018-03-24 04:59 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -213 days 19:04:02

Time elapsed

80:29:00

Time remaining

0:00:00

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