No testdata at current.

问题描述

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

输入

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

输出

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

Samples

3
0 0 0
1 0 0
0 0 0

3

Limitation

1s, 1024KiB for each test case.