对于偶数长度的排列$$$^{\text{∗}}$$$ $$$p$$$,可以执行以下过程:
- 初始化计数器 $$$c = 0.$$$
- 对于从 $$$1$$$ 到 $$$n 的每个 $$$i$$$,$$$ 要么将 $$$i \cdot p_i$$$ 添加到 $$$c$$$,要么从 $$$c$$$ 中减去 $$$i \cdot p_i$$$,或者什么都不做。
正式地,对于每个 $$$i \in \{1,\ldots,n\},$$$ 考虑集合 $$$S_i = \{-i \cdot p_i, 0, i \cdot p_i\}$$$ 并选择一些 $$$x_i \in S_i。$$$ 设置 $$$c_{\mathrm{final}} = \sum_{i = 1}^{n}x_i.$$$
您将获得一个 甚至 整数$$$n$$$。找到长度 $$$n$$$ 的任意排列,以便无论选择何种操作,最终值 $$$c_{\mathrm{final}}$$$ 都不会是 $$$1。$$$
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 25$$$)。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含一个 甚至 整数 $$$n \, (2 \le n \le 50)$$$ — 所需排列的长度。
输出
对于每个测试用例,输出 $$$n$$$ 整数 $$$p_1, \ldots, p_n \, (1 \le p_i \le n)$$$ — 满足条件的排列。
如果有多个解决方案,请打印其中任何一个。
示例
输入复制
3246
输出复制
2 1 2 3 4 1 5 4 6 2 1 3
注意
在第一个测试用例中,输出中给出的排列是 $$$[2,1].$$$ 计数器可以通过以下 $$$9$$$ 方式递增:
- $$$0 \xrightarrow{+2 \cdot 1} 2 \xrightarrow{+0} 2$$$
- $$$0 \xrightarrow{+0} 2 \xrightarrow{+1 \cdot 2} 2$$$
- $$$0 \xrightarrow{-2 \cdot 1} -2 \xrightarrow{+0} -2$$$
- $$$0 \xrightarrow{+0} 2 \xrightarrow{-1 \cdot 2} -2$$$
- $$$0 \xrightarrow{-2 \cdot 1} -2 \xrightarrow{+1 \cdot 2} 0$$$
- $$$0 \xrightarrow{+2 \cdot 1} 2 \xrightarrow{-1 \cdot 2} 0$$$
- $$$0 \xrightarrow{-2 \cdot 1} -2 \xrightarrow{-1 \cdot 2} -4$$$
- $$$0 \xrightarrow{+2 \cdot 1} 2 \xrightarrow{+1 \cdot 2} 4.$$$
- $$$0 \xrightarrow{+0} 0 \xrightarrow{+0} 0.$$$
我们可以证明第二个测试用例中给出的排列满足条件。但是,排列 $$$[1,2,3,4]$$$ 不满足条件,因为序列 $$0 \xrightarrow{+1 \cdot 1} 1 \xrightarrow{+0} 1 \xrightarrow{+0} 1 \xrightarrow{+0} 1$$ 最终导致 $$$c = 1$$$。