时间限制：1秒　　内存限制：256M

---

【题目描述】

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

　　　　　　　　0 0 0　　　　0 1 0
　　　　　　　　1 0 0　　　　1 0 1
　　　　　　　　0 0 0　　　　0 1 0

【输入格式】

　　输入的第一行为数据组数　\(T\)。每组数据的第一行为正整数 \(n\)；接下来的n行每行包含 \(n\) 个非 0 即 1 的整数，相邻整数间用一个空格隔开。

【输出格式】

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

【输入输出样例】

　Input

3
3
0 0 0
0 0 0
0 0 0
3
0 0 0
1 0 0
0 0 0
3
1 1 1
1 1 1
0 0 0

　Output

0
3
-1

【数据限制】

　　对于 \(100\%\) 的数据，\(T≤30，1≤n≤25\)

【来源】

　　Mr.he**