给定一个方阵 $$$A$$$,大小为 $$$n \times n$$$,其元素为整数。我们将第 $$$i$$$ 行和第 $$$j$$$ 列的交集上的元素表示为 $$$A_{i,j}$$$。
您可以对矩阵进行运算。在每个操作中,您可以选择一个整数 $$$k$$$,然后对于每个索引 $$$i$$$ ($$$1 \leq i \leq n$$$),将 $$$A_{i, k}$$$ 与 $$$A_{k, i}$$$ 交换。请注意,单元格 $$$A_{k, k}$$$ 保持不变。
例如,对于 $$$n = 4$$$ 和 $$$k = 3$$$,该矩阵将被转换如下:
运算 $$$k = 3$$$ 将蓝色行与绿色列交换。
您可以执行此操作任意次。找到执行任意次数的操作后可以获得的按字典顺序最小的矩阵$$$^\dagger$$$。
$$${}^\dagger$$$ 对于大小为 $$$n \times n$$$ 的两个矩阵 $$$A$$$ 和 $$$B$$$,令 $$$a_{(i-1) \cdot n + j} = A_{i,j}$$$ 和 $$$b_{(i-1) \cdot n + j} = B_{i,j}$$$。然后,当存在索引 $$$i$$$ ($$$1 \leq i \leq n^2$$$) 使得 $$$a_i < b_i$$$ 且对于所有索引 $$$j$$$ 使得 $$$1 \leq j < i$$$、$$$a_j = b_j$$$ 时,矩阵 $$$A$$$ 按字典顺序小于矩阵 $$$B$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 1000$$$) — 矩阵的大小。
接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含 $$$n$$$ 整数 $$$A_{i, 1}, A_{i, 2}, \dots, A_{i, n}$$$ ($$$1 \le A_{i, j} \le 10^9$$$) — 矩阵 $$$A$$$ 的描述。
保证所有测试用例的$$$n^2$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,打印 $$$n$$$ 行,每行包含 $$$n$$$ 整数 — 按字典顺序排列的最小矩阵。
示例
输入 #1
2 3 2 1 2 2 1 2 1 1 2 4 3 3 1 2 1 1 3 1 3 2 3 2 2 3 3 1
输出 #1
2 1 1 2 1 1 2 2 2 3 1 1 2 3 1 2 1 3 3 3 3 2 3 2 1
注意
请注意,在下面的每张图片中,矩阵都以蓝色行与绿色列交换的方式进行转换。
在第一个测试用例中,我们可以对 $$$k = 3$$$ 执行 $$$1$$$ 操作。矩阵将变换如下: