英文原题

C1. XOR Convenience (Easy Version)

• Time limit per test: 2 seconds

• Memory limit per test: 256 megabytes

• Input: standard input

• Output: standard output

This is the easy version of the problem. The difference between the versions is that in this version, $2≤i≤n−1$. Note that a correct solution for the hard version is not necessarily a correct solution for the easy version.

Given a natural number $n$. Find a permutation∗ of length $n$, such that for each $i (2≤i≤n−1)$ there exists a $j (i≤j≤n)$ such that $p_i = p_j ⊕ i †$.

It can be proven that under the constraints of the problem, there exists at least one suitable permutation $p$.

∗A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (2 appears twice in the array), and $[1,3,4]$ is also not a permutation (n=3 but there is 4 in the array).

$†⊕$ denotes the bitwise XOR operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t (1≤t≤10^4)$. The description of the test cases follows.

The only line of each test case contains a single integer $n (3≤n≤2⋅10^5)$.

It is guaranteed that the sum of n across all test cases does not exceed $2⋅10^5$.

Output

For each test case, output $n$ integers $p₁,p₂,…,pₙ$ — the permutation $p$.

If there are multiple solutions, you may output any of them.

Example

Input

2
3
6

Output

2 1 3
3 6 2 5 1 4

Note

In the first test case, the permutation $p=[2,1,3]$ is suitable since $p₂=1$ and $p₃⊕2=1$.

In the second test case, the permutation $p=[3,6,2,5,1,4]$ is suitable, as:

• $p₂=6=4⊕2=p₆⊕2$

• $p₃=2=1⊕3=p₅⊕3$

• $p₄=5=1⊕4=p₅⊕4$

• $p₅=1=4⊕5=p₆⊕5$

中文翻译

C1. XOR Convenience (Easy Version)

• 每个测试点时间限制：2 秒

• 每个测试点内存限制：256 兆字节

• 输入：标准输入

• 输出：标准输出

这是该问题的简单版本。不同版本之间的区别在于，在本版本中满足 $2≤i≤n−1$。请注意，针对困难版本的正确解法不一定适用于简单版本。

给定一个自然数 $n$。请找出一个长度为 $n$ 的排列$∗p$，使得对于每个 $i（2≤i≤n−1）$，都存在一个 $j（i≤j≤n）$满足 $pᵢ = pⱼ ⊕ i †$。

可以证明，在题目给定的约束条件下，至少存在一个符合要求的排列 $p$。

∗长度为 $n$ 的排列指的是一个由 n 个互不相同的整数组成的数组，这些整数的取值范围是 $1$ 到 $n$，顺序可以任意。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（数字 $2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 但数组中出现了 $4$）。

$†⊕$ 表示按位异或运算。

输入格式

每个测试包含多组测试用例。第一行输入测试用例的数量 $t（1≤t≤10⁴）$。接下来描述每组测试用例。

每组测试用例仅包含一行，输入一个整数 $n（3≤n≤2⋅10⁵）$。

保证所有测试用例的 $n$ 之和不超过 $2⋅10⁵$。

输出格式

对于每组测试用例，输出 $n$ 个整数 $p₁,p₂,…,pₙ$ —— 即满足要求的排列 $p$。

如果存在多个可行解，你可以输出任意一个。

样例

输入

2
3
6

输出

2 1 3
3 6 2 5 1 4

说明

在第一个测试用例中，排列 $p=[2,1,3]$ 是符合要求的，因为 $p₂=1$，且 $p₃⊕2=1$。

在第二个测试用例中，排列 $p=[3,6,2,5,1,4]$ 是符合要求的，原因如下：

• $p₂=6=4⊕2=p₆⊕2$

• $p₃=2=1⊕3=p₅⊕3$

• $p₄=5=1⊕4=p₅⊕4$

• $p₅=1=4⊕5=p₆⊕5$

C1. 题解

思路

题目要求对于所有的 $2 \le i \le n-1$，必须存在一个 $j (i \le j \le n)$ 使得 $p_i = p_j \oplus i$。 利用异或的性质 ，原条件等价于 $p_j = p_i \oplus i$。注意到，当 $i$ 为 $n - 1$ 时， $j$ 只能是 $n$，所以我们有以下思路：

由于我们需要构造任意一个满足条件的排列，我们可以尝试更贪心一点。 我们不妨让对于所有的 $i$，满足条件的 $j$ 都固定为 $n$。 我们希望构建一个排列，使得对于所有 $2 \le i \le n-1$，都有： $p_i=p_n \oplus i$ 为了方便计算，我们设 $p_n = 1$。 那么对于 $2 \le i \le n-1$，中间的元素就确定为 $p_i = i \oplus 1$。 我们需要检查按照 $p_i = i \oplus 1$ 生成的中间段数字，再加上 $p_n=1$，最后缺了哪个数字，就把那个数字填给 $p_1$。

• 异或 1 的性质：x $\oplus$ 1 的作用是：如果 $x$ 是偶数，则变为 $x+1$。如果 $x$ 是奇数，则变为 $x-1$。它实际上是在相邻的偶数和奇数之间互换（$2\leftrightarrow 3,\ 4 \leftrightarrow 5,\ …$）。

• 情况1：n 是偶数

  这是一个包含若干个完整偶奇对的序列。

  对这些数进行 $\oplus 1$ 操作，只是组内互换，数值集合依然是 $\{2, 3, \dots, n-1\}$。

  加上 $p_n=1$，目前用掉的数是 $\{1, 2, \dots, n-1\}$。

  缺少的数是 n。所以令 $p_1 = n$。

• 情况2：n 是奇数

  这个区间内的数是 $[2, 3], \dots, [n-3, n-2]$ 以及单独剩下的偶数 $n-1$。

  前面的成对数字 $\oplus 1$ 后依然在集合内。

  单独的 $n-1$（偶数）操作后变为 $(n-1) \oplus 1 = n$。

  所以中间段生成的数值集合是 $\{2, 3, \dots, n-2, n\}$。

  加上 $p_n=1$，目前用掉的数是 $\{1, 2, \dots, n-2, n\}$。

  缺少的数是 $n-1$。所以令 $p_1 = n-1$。

方法

1. 判断奇偶并填充开头元素：

   • 若 n 为偶数，nums 先压入 $n$。

   • 若 n 为奇数，nums 先压入 $n-1$。

2. 填充中间： 遍历 $i$ 从 $2$ 到 $n-1$，压入 $i \oplus 1$。

3. 填充结尾： 最后压入 $1$。

4. 输出： 打印 nums 数组。

复杂度

时间复杂度： O(N)

空间复杂度： O(N)

代码实现

C++：

#include <iostream>
#include <vector>
using namespace std;
​
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
​
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> nums;
        
        //偶数缺n，奇数缺n-1，压入数组中
        if (n % 2 == 0) nums.push_back(n);
        else nums.push_back(n - 1);
        
        //构造中间部分，p[i] = i ^ 1
        for (int i = 2; i < n; i++) {
            nums.push_back(i ^ 1);
        }
        
        //末尾p[n] = 1
        nums.push_back(1);
        
        for (int i = 0; i < nums.size(); i++) {
            cout << nums[i] << " ";
        }
        cout << endl;
    }
    return 0;
}