题目描述

小 Z 和小 Y 又开始玩一个战争游戏了，在一个大小为 $n \times n$ 的棋盘上存在许多他们两人控制的士兵。

小 Z 控制的士兵编号为 $0$ ， 小 Y 控制的士兵编号为 $1$。

小 Z 拥有一个技能，可以将自己的士兵送给小 Y，也就是将自己的士兵转换成小 Y 的士兵

而正因为小 Z 拥有这个技能，所以他有一种隐藏的获胜方式：

如果这个棋盘中每个士兵周围都有偶数个属于小 Y 的士兵（可以是 $0$ 个)，那么这局游戏他就能获得胜利。

「注意」

• 上述要求每一个士兵周围都要有偶数个小 Y 的士兵（可以是 $0$ 个），即每一个 $0$ 和 $1$ 士兵都要满足。
• 这里周围的定义指的是上、下、左、右四个方向（如果存在）。

但是毕竟使用技能将自己的士兵送给对方这个行为是在给对方送战力，是不太被理解的，如果转化士兵的次数过多，小 Y 容易发现端倪。

所以小 Z 希望知道自己最少需要转化多少个士兵，才能让自己获得胜利？

输入格式

输入第一行包含一个正整数 $n$，表示棋盘大小 $n \times n$。

接下来 $n$ 行每行 $n$ 个整数中间用空格隔开，输入只包含 $0$ 和 $1$，分别表示小 Z 控制的士兵和小 Y 控制的士兵。

输出格式

输出一个数，表示小 Z 最少需要转化的士兵数量，若无解则输出 $-1$。

样例

3
0 0 0
1 0 0
0 0 0

3

3
0 1 0
1 0 0
0 0 1

4

3
0 0 0
0 0 0
0 0 0

0

提示

【样例 1 解释】

转换三次（$0\rightarrow 1$）使得棋盘变为：

0 1 0
1 0 1
0 1 0

满足每一个士兵周围有偶数个 $1$（小 Y 控制的士兵）。

【样例 2 解释】

转换四次（$0\rightarrow 1$）使得棋盘变为：

1 1 0
1 1 1
0 1 1

【样例 3 解释】

棋盘已经满足条件，不需要转换。

满足每一个士兵周围有偶数个 $1$（小 Y 控制的士兵）。

【数据范围】

对于 $60\%$ 的数据，$n \leq 6$。

对于 $100\%$ 的数据，$2 \le n \leq 18$。