CF1716B.Permutation Chain

A permutation of length $n$ is a sequence of integers from $1$ to $n$ such that each integer appears in it exactly once.

Let the fixedness of a permutation $p$ be the number of fixed points in it — the number of positions $j$ such that $p_j = j$, where $p_j$ is the $j$-th element of the permutation $p$.

You are asked to build a sequence of permutations $a_1, a_2, \dots$, starting from the identity permutation (permutation $a_1 = [1, 2, \dots, n]$). Let's call it a permutation chain. Thus, $a_i$ is the $i$-th permutation of length $n$.

For every $i$ from $2$ onwards, the permutation $a_i$ should be obtained from the permutation $a_{i-1}$ by swapping any two elements in it (not necessarily neighboring). The fixedness of the permutation $a_i$ should be strictly lower than the fixedness of the permutation $a_{i-1}$.

Consider some chains for $n = 3$:

• $a_1 = [1, 2, 3]$, $a_2 = [1, 3, 2]$ — that is a valid chain of length $2$. From $a_1$ to $a_2$, the elements on positions $2$ and $3$ get swapped, the fixedness decrease from $3$ to $1$.
• $a_1 = [2, 1, 3]$, $a_2 = [3, 1, 2]$ — that is not a valid chain. The first permutation should always be $[1, 2, 3]$ for $n = 3$.
• $a_1 = [1, 2, 3]$, $a_2 = [1, 3, 2]$, $a_3 = [1, 2, 3]$ — that is not a valid chain. From $a_2$ to $a_3$, the elements on positions $2$ and $3$ get swapped but the fixedness increase from $1$ to $3$.
• $a_1 = [1, 2, 3]$, $a_2 = [3, 2, 1]$, $a_3 = [3, 1, 2]$ — that is a valid chain of length $3$. From $a_1$ to $a_2$, the elements on positions $1$ and $3$ get swapped, the fixedness decrease from $3$ to $1$. From $a_2$ to $a_3$, the elements on positions $2$ and $3$ get swapped, the fixedness decrease from $1$ to $0$.

Find the longest permutation chain. If there are multiple longest answers, print any of them.

长度为 $n$ 的一个排列是指由 $1$ 到 $n$ 的整数组成的序列，其中每个整数恰好出现一次。

定义一个排列 $p$ 的**不动点数（fixedness）**为该排列中不动点的个数——即满足 $p_j = j$ 的位置 $j$ 的个数，其中 $p_j$ 表示排列 $p$ 的第 $j$ 个元素。

你需要构造一个排列序列 $a_1, a_2, \dots$，起始于恒等排列（即 $a_1 = [1, 2, \dots, n]$）。我们称其为一个排列链（permutation chain）。因此，$a_i$ 是长度为 $n$ 的第 $i$ 个排列。

对每个 $i \geq 2$，排列 $a_i$ 必须由排列 $a_{i-1}$ 通过交换其中任意两个元素（不一定是相邻元素）得到；且 $a_i$ 的不动点数必须严格小于 $a_{i-1}$ 的不动点数。

考虑 $n = 3$ 的一些例子：

• $a_1 = [1, 2, 3]$，$a_2 = [1, 3, 2]$ —— 这是一个长度为 $2$ 的合法链。从 $a_1$ 到 $a_2$，位置 $2$ 和 $3$ 上的元素被交换，不动点数从 $3$ 减少到 $1$。
• $a_1 = [2, 1, 3]$，$a_2 = [3, 1, 2]$ —— 这不是一个合法链。对于 $n = 3$，第一个排列必须始终是 $[1, 2, 3]$。
• $a_1 = [1, 2, 3]$，$a_2 = [1, 3, 2]$，$a_3 = [1, 2, 3]$ —— 这不是一个合法链。从 $a_2$ 到 $a_3$，位置 $2$ 和 $3$ 上的元素被交换，但不动点数从 $1$ 增加到了 $3$。
• $a_1 = [1, 2, 3]$，$a_2 = [3, 2, 1]$，$a_3 = [3, 1, 2]$ —— 这是一个长度为 $3$ 的合法链。从 $a_1$ 到 $a_2$，位置 $1$ 和 $3$ 上的元素被交换，不动点数从 $3$ 减少到 $1$；从 $a_2$ 到 $a_3$，位置 $2$ 和 $3$ 上的元素被交换，不动点数从 $1$ 减少到 $0$。

请找出最长的排列链。如果存在多个最长的链，输出任意一个即可。

The first line contains a single integer $t$ ($1 \le t \le 99$) — the number of testcases.

The only line of each testcase contains a single integer $n$ ($2 \le n \le 100$) — the required length of permutations in the chain.

第一行包含一个整数 $t$（$1 \le t \le 99$）—— 测试用例的数量。

每个测试用例仅有一行，包含一个整数 $n$（$2 \le n \le 100$）—— 所需链中排列的长度。

For each testcase, first, print the length of a permutation chain $k$.

Then print $k$ permutations $a_1, a_2, \dots, a_k$. $a_1$ should be an identity permutation of length $n$ ($[1, 2, \dots, n]$). For each $i$ from $2$ to $k$, $a_i$ should be obtained by swapping two elements in $a_{i-1}$. It should also have a strictly lower fixedness than $a_{i-1}$.

对于每个测试用例，首先输出一个排列链的长度 $k$。

然后输出 $k$ 个排列 $a_1, a_2, \dots, a_k$。其中 $a_1$ 应为长度为 $n$ 的单位排列（即 $[1, 2, \dots, n]$）。对每个从 $2$ 到 $k$ 的 $i$，$a_i$ 应通过交换 $a_{i-1}$ 中的两个元素得到，且其固定点数（fixedness）必须严格小于 $a_{i-1}$ 的固定点数。