Background

最近我总是辗转反侧 难以入眠 对我们曾有过的愿景浮想联翩

Description

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

    0   0   0              0   1   0
    1   0   0              1   0   1
    0   0   0              0   1   0
      （a）                  （b） 

Format

Input

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

Output

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

Sample

Input

1 
3 
0 0 0 
1 0 0 
0 0 0

Output

3

Limitation

1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST