长度 $$$n$$$ 的排列是从 $$$1$$$ 到 $$$n$$$ 的整数序列,使得每个整数在其中恰好出现一次。
令排列 $$$p$$$ 的固定性为其中固定点的数量 - 使得 $$$p_j = j$$$ 的位置数量 $$$p_j = j$$$,其中 $$$p_j$$$ 是排列 $$$p$$$ 的第 $$$j$$$ 个元素。
要求您从恒等排列(排列 $$$a_1 = [1, 2, \dots, n]$$$)开始构建排列序列 $$$a_1, a_2, \dots$$$。我们称之为排列链。因此,$$$a_i$$$ 是长度$$$n$$$ 的第$$$i$$$ 排列。
对于从 $$$2$$$ 开始的每个 $$$i$$$,排列 $$$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$$$。
找到最长的排列链。如果有多个最长的答案,请打印其中任何一个。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 99$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) - 链中排列所需的长度。
输出
对于每个测试用例,首先打印排列链 $$$k$$$ 的长度。
然后打印 $$$k$$$ 排列 $$$a_1, a_2, \dots, a_k$$$。 $$$a_1$$$ 应该是长度为 $$$n$$$ ($$$[1, 2, \dots, n]$$$) 的恒等排列。对于从$$$2$$$到$$$k$$$的每个$$$i$$$,$$$a_i$$$应该通过交换$$$a_{i-1}$$$中的两个元素来获得。它的固定性也应该严格低于 $$$a_{i-1}$$$。
示例
输入 #1
2 2 3
输出 #1
2 1 2 2 1 3 1 2 3 3 2 1 3 1 2