Troyangles

This problem is translated from CCO 2014 Day1 T1 "Troyangles".

Troy loves triangles and he especially loves counting triangles. He has an \(N \times N\) grid consisting of the characters . and #. Your task is to count the number of triangles that are composed solely of # characters in the grid.

A triangle of height \(h\) (where \(h\ge 1\)) is defined as follows:

\[ \begin{array}{c} \,\#\\[5pt] \#\quad\#\#\#\\[5pt] \#\#\#\#\#\\[5pt] \vdots \end{array} \]

More formally, a triangle with height \(h\) consists of \(h\) rows. In the \(i\)-th row (with \(1 \le i \le h\)), there are \(2i-1\) consecutive # characters, and these rows are centered with respect to a vertical line passing through the apex of the triangle.

Your task is to count every occurrence of such a triangle in the grid. A triangle is considered to occur if all the required grid cells (for some height \(h\)) contain the character #.

inputFormat

The first line contains an integer \(N\) representing the size of the grid. The following \(N\) lines each contain a string of length \(N\), consisting only of the characters . and #.

outputFormat

Output a single integer representing the number of triangles found in the grid.

sample

1
#

1

</p>