Little T is very fond of matrices, especially permutation matrices, which are matrices with exactly one $1$ in each row and each column, and $0$ elsewhere. Now, she is presented with an $N \times N$ integer matrix $A$. She wants to know if there exists a set of permutation matrices $B_1, B_2, \dots, B_m$ ($\forall i \ne j, B_i \ne B_j$) such that there is one and only one set of non-negative integer coefficients $\alpha_1, \alpha_2, \dots, \alpha_m$ satisfying $A = \alpha_1B_1 + \alpha_2B_2 + \dots + \alpha_m B_m$.
Furthermore, because Little T does not like overly complex solutions, if a solution exists, she requires that the number of distinct permutation matrices in your solution is not too large. Specifically, if a solution exists, she accepts any solution where $m \leq N^2$.
Input
The first line contains an integer $T$, representing the number of test cases.
For each test case, the first line contains an integer $N$. The next $N$ lines each contain $N$ integers, representing the elements of matrix $A$ at the corresponding positions. It is guaranteed that $A$ is not a zero matrix.
Output
For each test case, if no solution exists, output a single line containing "-1". Otherwise, first output an integer $m$ on one line. Then, output $m$ lines, each containing $N+1$ integers. The first integer in the $i$-th line is $\alpha_i$, and the $j$-th integer (for $j > 1$) is the column index of the $1$ in the $(j-1)$-th row of $B_i$.
Examples
Input 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 100Output 1
1
1 1 2
-1
2
1 1 2
1 2 1
-1
2
100 1 2
99 2 1Input 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 1Output 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 1Subtasks
- 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$.
For $100\%$ of the data, $1 \leq T \leq 10$, $-2 \times 10^7 \leq A_i \leq 2 \times 10^7$.