给定一个 $n \times n$ 的整数矩阵 $A$，你需要找到两个 $n \times n$ 的整数矩阵 $B$ 和 $C$，使得 $B \cdot C = A$ 且 $\det(B) = \det(C) \neq 0$。可能存在多个解，也可能无解。

注意：$\det(M)$ 表示矩阵 $M$ 的行列式。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10\,000$)，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 4$)，表示给定矩阵的大小。

接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $A_{i,j}$ ($|A_{i,j}| \le 10$，其中 $1 \le j \le n$)，表示给定的矩阵。

输出格式

对于每个测试用例：

如果存在解，第一行必须包含一个字符串 “Yes”（不含引号），否则输出 “No”（不含引号）。如果存在解：

接下来的 $n$ 行包含 $n$ 个整数 $B_{i,j}$ ($|B_{i,j}| \le 10^{18}$)，表示矩阵 $B$。

接下来的 $n$ 行包含 $n$ 个整数 $C_{i,j}$ ($|C_{i,j}| \le 10^{18}$)，表示矩阵 $C$。

如果存在多个解，输出其中任意一个即可。

样例

输入 1

3
2
2 0
0 2
2
2 1
1 2
1
1

输出 1

Yes
2 0
0 1
1 0
0 2
No
Yes
-1
-1