题目描述

你说的对，但是前缀异或是一个模 4 规律的结果！

给定一个正整数 $n$，请构造长度为 $n$ 的一个排列 $p=(p_1,p_2,\ldots,p_n)$，使得

$$\sum_{i=1}^n \bigoplus_{j=1}^i p_j$$

的值最小。其中 $\bigoplus$ 表示按位异或。

长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的序列。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但出现了 $4$）。

输入描述

本题包含多个测试数据，第一行包含一个整数 $T$（$1 \le T \le 3 \times 10^3$），表示测试数据组数。

对于每一组测试用例，仅包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。

保证所有测试用例 $n$ 的总和不超过 $2 \times 10^5$。

输出描述

对于每个测试用例，输出一个排列 $p=(p_1,p_2,\ldots,p_n)$，使得

$$\sum_{i=1}^n \bigoplus_{j=1}^i p_j$$

的值最小。排列中的数用空格隔开。

如果有多个满足条件的排列，输出任意一个均可。

样例

3
3
1
7

1 3 2
1
4 5 3 2 6 7 1

注释

以第一个测试用例为例：

如果 $p=(1,3,2)$，则

$$\sum_{i=1}^n \bigoplus_{j=1}^i p_j = 1 + (1 \oplus 3) + (1 \oplus 3 \oplus 2) = 1+2+0=3$$

该值不能小于 $3$，所以输出 $p=(1,3,2)$ 是正确的。输出 $p=(2,3,1)$ 也是正确的。