题目描述

给定一个 01 矩阵，其中你可以在 0 的位置放置攻击装置。每一个攻击装置 $(x,y)$ 都可以按照「日」字攻击其周围的 $8$ 个位置$(x-1,y-2),(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1),(x+1,y+2),(x+2,y+1)$。

求在装置互不攻击的情况下，最多可以放置多少个装置。

输入格式

第一行一个整数 $n$，表示矩阵大小为 $n\times n$。接下来 $n$ 行每一行一个长度 $n$ 的 01 串，表示矩阵。

输出格式

一个整数，表示在装置互不攻击的情况下最多可以放置多少个装置。

样例输入

3
010
000
100

样例输出

4

数据规模与提示

对于 $100\%$ 的数据，$n\le 200$。