给你一个 $n \times n$ 的 $01$ 矩阵（每个元素非 $0$ 即 $1$），你的任务是把尽量少的 $0$ 变成 $1$，使得原矩阵便为偶数矩阵（矩阵中每个元素的上、下、左、右的元素（如果存在的话）之和均为偶数）。

### 输入格式

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

### 输出格式

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