CSES - Beautiful Subgrids
  • 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 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