BaoBao the Witch 被困在一个 $n$ 行 $n$ 列的迷宫中，其中第 $i$ 行第 $j$ 列的单元格高度为 $h_{i,j}$。为了走出迷宫，BaoBao 必须找到一条恰好经过每个单元格一次的路径。每次她只能移动到与当前单元格共享一条边的相邻单元格。众所周知，BaoBao 非常懒，所以每次她向上爬（即从高度较小的单元格移动到高度较大的单元格）时，她的幸福值都会降低。作为她的帮手，你的任务是找到一条合法的路径，使得沿着路径移动时，BaoBao 向上爬的次数不超过她向下爬的次数。

更正式地说，你需要找到一个序列 $(x_1, y_1), (x_2, y_2), \dots, (x_{n^2}, y_{n^2})$ 满足：

• 对于所有 $1 \le i \le n^2$，$1 \le x_i, y_i \le n$；
• 对于所有 $1 \le i, j \le n^2$，$i \neq j$，$(x_i, y_i) \neq (x_j, y_j)$；
• 对于所有 $2 \le i \le n^2$，$|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1$；
• $\sum_{i=2}^{n^2} [h_{x_{i-1}, y_{i-1}} < h_{x_i, y_i}] \le \sum_{i=2}^{n^2} [h_{x_{i-1}, y_{i-1}} > h_{x_i, y_i}]$，其中 $[P]$ 在 $P$ 为真时等于 1，为假时等于 0。

此外，你发现所有单元格的高度是 $n^2$ 的一个排列，因此你只需要输出合法路径中每个单元格的高度即可。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($2 \le n \le 64$)，表示迷宫的大小。

接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $h_{i,1}, h_{i,2}, \dots, h_{i,n}$ ($1 \le h_{i,j} \le n^2$)，其中 $h_{i,j}$ 表示第 $i$ 行第 $j$ 列单元格的高度。保证输入中的所有整数构成 $n^2$ 的一个排列。

输出格式

对于每组测试数据，输出一行，包含 $n^2$ 个由空格分隔的整数，表示合法路径中每个单元格的高度。如果存在多个合法答案，你可以输出其中任意一个。可以证明答案总是存在的。

请注意，不要在每行末尾输出多余的空格，否则你的答案可能会被判定为错误！

样例

输入 1

1
2
4 3
2 1

输出 1

4 3 1 2