题目描述

wwx 和 lhs 又开始玩一个战争游戏了，在一个大小为 $n * n$ 的棋盘上存在许多她们两人控制的士兵

wwx 控制的士兵编号为 $0$ ， lhs 控制的士兵编号为 $1$

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

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

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

P.S. 这里的周围是指上下左右

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

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

输入格式

输入第一行包含一个正整数 $n$，表示棋盘大小 $n * n$ 接下来 $n$ 行每行 $n$ 个整数中间用空格隔开，输入只包含 $0$ 和 $1$，分别表示 wwx 控制的士兵和 lhs 控制的士兵

输出格式

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

数据范围

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

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

样例输入

3
0 0 0
1 0 0
0 0 0

样例输出

3

样例解释

转换三次使得棋盘变为

3
0 1 0
1 0 1
0 1 0