偶数矩阵

给你一个 $n×n$ 的01矩阵（每个元素非 $0$ 即 $1$），你的任务是把尽量少的 $0$ 变成 $1$，使得每个元素的上、下、左、右的元素（如果存在的话）之和均为偶数。比如，左边所示的矩阵至少要把 $3$ 个 $0$ 变成 $1$，最终右边图所示，才能保证其为偶数矩阵。

输入格式

第一行是正整数 $n$，接下来的 $n$ 行每行包含 $n$ 个非 $0$ 即 $1$ 的整数，相邻整数间用一个空格隔开。

输出格式

对于每组数据，输出被改变的元素的最小个数。如果无解，应输出 $-1$。

3
0 0 0
1 0 0 
0 0 0

3

提示

数据范围与提示

$1≤n≤15$

时间限制: 1000ms

内存限制: 128MB