当前没有测试数据。

D. Blackslex 和企鹅文明

题目描述

企鹅是具有文明的生物，它们通过排列进行交流。作为企鹅研究员，Blackslex 必须研究它们的交流方式。

给定整数 $n$，考虑数组 $[0, 1, \ldots, 2^n - 1]$ 的排列 $p$。定义：

$$S(p) = \sum_{i=0}^{2^n - 1} \text{popcount}(p_0 \& p_1 \& \cdots \& p_i)$$

其中 $\text{popcount}(z)$ 表示 $z$ 的二进制表示中 $1$ 的个数（例如，$\text{popcount}(5) = 2$，因为 $5 = 101_2$ 的二进制表示中有两个 $1$ 位），$\&$ 表示按位与运算（参考 按位与运算）。

如果一个排列能最大化 $S(p)$，则称其为神圣排列。请找出字典序最小的神圣排列。

补充说明

$^*$ 长度为 $m$ 的排列是指由 $m$ 个不同整数组成的数组，这些整数恰好是 $0$ 到 $m-1$（本题中 $m = 2^n$）。例如，$[2,3,1,5,4]$ 是排列，但 $[1,2,2]$ 不是（2 出现两次），$[1,3,4]$ 也不是（$m=3$ 但包含 4）。

$^\dagger$ 若两个长度相同的数组 $a$ 和 $b$，在第一个不同的位置上，$a$ 的元素小于 $b$ 对应的元素，则称 $a$ 字典序小于 $b$。

输入格式

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

保证所有测试用例的 $2^n$ 之和不超过 $2^{16}$。

输出格式

对于每个测试用例，输出 $2^n$ 个整数 $p_0, p_1, \ldots, p_{2^n - 1}$—— 所求的排列。

样例输入

2
1
2

样例输出

1 0
3 1 0 2

说明

对于第一个测试用例，有两个可能的排列：

• $p = [0, 1]$，$S(p) = 0$
• $p = [1, 0]$，$S(p) = 1$

对于第二个测试用例，$S([3, 1, 0, 2]) = 3$，该排列是神圣的。还有其他神圣排列，例如 $[3, 2, 0, 1]$，但它们的字典序都不是最小的。