You are given an \(n×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 \ \leq \ n \ \leq \ 3000\)

Example

Sample input

5
00010
11111
00110
11001
00010

Sample output

4