PLUSEVI - How Many Plusses

no tags 

Mirko is a strange boy so he has written down a square matrix full of ones and zeroes. Now he is interested in how many plusses there are in his matrix.

A plus is a square such that its side has an odd length greater than 1 and all of its cells are zero, except for the middle row and the middle column: they must be full of ones. For example, in the matrix below there are two plusses, one inside the other:

00100
00100
11111
00100
00100

Input

In the first line there is an integer N ≤ 2000, dimension of the square matrix.

The next N lines are the rows of the matrix.

Output

Print the number of plusses appearing in the matrix.

Example

Input:
8
00010000
00010000
00010000
11111111
00010000
00010010
00010111
00010010

Output: 3

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2012-12-25 15:48:03

@Ehor Nechiporenko: No, that not true... Max matix size is 2000x2000. AC on first try with 2000x2000 static array...

Ehor Nechiporenko: 2012-12-24 15:23:01

Important!!! Seems like matrix size could be greater than 200!
I have received SIGSEGV error, until made matrix dynamic!

Radhakrishnan Venkataramani: 2011-09-14 09:33:35

Nice Problem !!!
I came with two solutions !
I wonder ! How many possible solutions are there !!!


Added by:Adrian Satja Kurdija
Date:2011-05-21
Time limit:1s-4.595s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Croatian junior team selection test 2011