Troyangles

Interview

Time limit1sMemory limit256 MB

Summary

Count all centered triangles of `#` cells in an N-by-N grid where row i of a height-h triangle holds 2i-1 cells.

Level: Medium4 of 10
Topics: Dynamic programming, Matrix
Solved: No attempts yet

Problem

Troy loves triangles. You have an N-by-N grid of . or # cells. Count the triangles formed only by # cells. A triangle of height h has h rows; row i contains 2i − 1 # characters centered on a vertical axis.

Input

The first line contains N (1 ≤ N ≤ 2000). The next N lines contain the grid.

Output

Print the number of triangles in the grid.

Examples2

Example 1
Input
```
5
.....
.###.
.###.
#####
.....
```
Expected output
```
13
```
Example 2
Input
```
1
#
```
Expected output
```
1
```