小 T 特别喜欢矩阵，尤其是置换矩阵，即每行每列恰有一个 $1$，其余位置为 $0$ 的矩阵。现在她的面前有一个 $N \times N$ 的整数矩阵 $A$。她想知道，是否存在一组置换矩阵 $B_1, B_2, \cdots, B_m$（$\forall i \ne j, B_i \ne B_j$），对于这一组置换矩阵，有且仅有一组非负整系数 $\alpha_1, \alpha_2, \cdots, \alpha_m$，使得 $A = \alpha_1B_1 + \alpha_2B_2 + \cdots + \alpha_m B_m$

并且由于小 T 不喜欢过于复杂的解，在有解的情况下，她希望你给的解中置换矩阵的种类不能过多。具体地，倘若有解，她接受 $m \leq N^2$ 的任意一组解。

输入格式

第一行，一个整数 $T$，表示数据组数。

对于每一组数据，第一行一个整数 $N$，接下来 $N$ 行，每行 $N$ 个整数表示矩阵 $A$ 中对应位置的元素。数据保证 $A$ 不为零矩阵。

输出格式

对于每组数据，如果不存在解，则输出一行 “-1”（不包含引号）；否则，先输出一行一个整数 $m$，接下来 $m$ 行，每行 $N+1$ 个整数，其中第 $i$ 行第一个整数为 $\alpha_i$，第 $j>1$ 个整数为 $B_i$ 中第 $j-1$ 行的 $1$ 的列号。

样例数据

样例 1 输入

5
2
1 0
0 1
2
1 1
1 0
2
1 1
1 1
2
-1 0
0 -1
2
100 99
99 100

样例 1 输出

1
1 1 2
-1
2
1 1 2
1 2 1
-1
2
100 1 2
99 2 1

样例 2 输入

5
3
1 2 4
4 0 4
3 3 26962
3
4 0 -6
0 1 3
-3 0 -2
3
1 1 2
0 2 2
3 1 0
3
3 3 5
6 4 1
2 4 5
3
4 4 5
3 3 7
6 6 1

样例 2 输出

-1
-1
3
1 1 3 2
1 2 3 1
2 3 2 1
5
3 1 2 3
1 3 2 1
2 2 1 3
4 3 1 2
1 2 3 1
5
1 1 2 3
3 1 3 2
3 3 1 2
4 2 3 1
2 3 2 1

子任务

• Subtask 1 (30 pts): $1 \leq N \leq 5$。
• Subtask 2 (30 pts): $1 \leq N \leq 30$。
• Subtask 3 (40 pts): $1 \leq N \leq 50$。

对于 $100\%$ 的数据，$1 \leq T \leq 10$，$-2 \times 10^7 \leq A_i \leq 2 \times 10^7$。