为了庆祝纵向拜特兰（Vertical Byteland）与横向拜特兰（Horizontal Byteland）合并十六周年，一场盛大的游行将穿过首都的街道。宫廷编舞家 Bytelon 决定设计一套全新的国舞——Byterek 的特殊编舞，以纪念这一盛事。

Byterek 由 $n^2$ 名舞者在一个大小为 $n \times n$ 的正方形方阵中表演。它由一系列纵向阶段（vertical phases）和横向阶段（horizontal phases）组成。在舞蹈过程中，舞者们可以自由地相互交换位置，但有一个条件：在纵向阶段，只允许在舞者各自所在的列内进行交换；在横向阶段，只允许在各自所在的行内进行交换。

这套编舞还承载着另一个旨在取悦国王 Byteasar 的寓意。每位舞者都将穿上特定颜色的服装，使得从皇家阳台上看去，方阵会呈现出一幅画面。Bytelon 希望这幅画面在舞蹈开始时看起来像纵向拜特兰的国旗，而在舞蹈结束时看起来像横向拜特兰的国旗。不幸的是，这个任务对他来说似乎太难了，特别是为了不让 Byteasar 感到厌烦，舞蹈应该包含尽可能少的阶段。请帮助 Bytelon，编写一个程序来生成 Byterek 的各个阶段。

输入格式

第一行包含一个整数 $Z \le 100$，表示接下来要描述的测试用例数量。

每个测试用例的第一行包含一个整数 $n$，表示方阵的行数和列数。

接下来的 $n$ 行，每行包含 $n$ 个整数，描述舞者的初始排列。$[1, n^2]$ 中的每个数字在此描述中仅出现一次，代表该舞者在最终排列中期望达到的位置。这意味着最终排列是一个每一行和每一列都已排序的表格，正如样例测试中所示。

输出格式

对于每个测试用例，程序的第一行应输出一个整数 $k$——Byterek 的最少阶段数。

接着输出 $k$ 个后续阶段的排列描述。

一个排列的描述由 $n$ 行组成，每行包含 $n$ 个整数，其中 $[1, n^2]$ 中的每个整数恰好出现一次。如果 $k > 0$，则第一个排列必须是可以通过 Byterek 的一个阶段从输入中给出的初始排列达到的。下一个排列应该可以从前一个排列达到，依此类推。最后一个排列必须等于已排序的表格。纵向和横向阶段的顺序是任意的。

数据范围

$n \in [1, 500]$，所有测试用例中 $n$ 的总和不超过 $1000$。

样例

输入样例 1

3
2
2 3
4 1
3
9 2 7
8 1 4
6 5 3
2
1 2
3 4

输出样例 1

2
2 1
4 3
1 2
3 4
3
2 7 9
8 1 4
5 6 3
2 1 3
5 6 4
8 7 9
1 2 3
4 5 6
7 8 9
0