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