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

You are given an n \times n grid whose each square is either black or white. A subgrid is called *beautiful* if its height and width is at least two 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