Number of Pluses

Time limit1sMemory limit128 MB

Summary

Count all plus-shaped patterns of odd size at least 3 in an N x N binary matrix, where every cell outside the cross must be 0.

Level: Medium6 of 10
Topics: Dynamic programming, Matrix, Array
Solved: No attempts yet

Problem

Sanggeun likes writing 0s and 1s in a square matrix. This time, he wants to count how many plus shapes are contained in the given matrix.

A plus is a square with an odd side length greater than 1. In that square, every cell in the middle row and the middle column must be 1, and every other cell must be 0. The matrix below contains two pluses.

Given the matrix, count the number of pluses it contains.

Input

The first line contains the size N of the matrix. (3 ≤ N ≤ 2000)

Each of the next N lines contains a length-N string consisting of 0s and 1s.

Output

Print the number of pluses contained in the given matrix.

Examples2

Example 1
Input
```
5
00100
00100
11111
00100
00100
```
Expected output
```
2
```

Example 2

Input

Expected output