**Time limit:**1.00 s**Memory limit:**512 MB

*beautiful*if it has at least four squares and all of its corners are black. How many beautiful subgrids are there within the given grid?

**Input**

The first input line has an integer $n$: the size of the grid.

Then there are $n$ lines describing the grid:

`1`

means that a square is black and `0`

means it is white.**Output**

Print the number of beautiful subgrids.

**Constraints**

- $1 \le n \le 3000$

**Example**

Input:

`5`

00010

11111

00110

11001

00010

Output:

`4`