## Day 1, Problem 1: Troyangles

Troy loves triangles. He especially likes counting triangles. He has an N-by-N grid consisting of either "`.`" or "`#`" characters. Help him count the number of triangles formed only by "`#`" characters in the grid. Triangles are of the form

```              #
#      ###
#,   ###,   #####,   etc.
```

More formally, a triangle of height h consists of h rows for some positive integer h. The i-th row contains 2i − 1 "`#`" characters for i = 1, …, h. The rows are centred above each other so that they are symmetrically about a vertical line down their middle.

### Input

The first line contains the number N (1 ≤ N ≤ 2000) representing the size of the grid. The next N lines each contain N characters as described above.

You can assume that for test cases worth 20% of the marks, N ≤ 50.

### Output

Output the number of triangles in the grid.

```5
.....
.###.
.###.
#####
.....
```

```16
```

### Explanation

There are 11 triangles of height one, 4 triangles of height two and 1 triangle of height three.

Point Value: 10 (partial)
Time Limit: 1.00s
Memory Limit: 64M