CF2179D.Blackslex and Penguin Civilization

Penguins are civilized creatures that communicate using permutations. Blackslex, as a penguin researcher, must study their means of communication.

For a given integer $n$, consider permutations$^{\text{∗}}$ $p$ of the array $[0, 1, \ldots, 2^n - 1]$. Define $$S(p) \;=\; \sum_{i=0}^{2n-1} \operatorname{popcount}\!\bigl(p_0 \mathbin{\&} p_1 \mathbin{\&} \cdots \mathbin{\&} p_i\bigr),$$ where $\operatorname{popcount}(z)$ is the number of $1$-bits in the binary representation of $z$ (for instance, $\operatorname{popcount}(5) = 2$ because $5 = 101_2$ has two $1$-bits in the binary representation), and $\&$ denotes the bitwise AND operation. .

A permutation is considered sacred if it maximizes $S(p)$. Find the lexicographically minimal$^{\text{†}}$ sacred permutation.

$^{\text{∗}}$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).

$^{\text{†}}$An array $a$ is lexicographically smaller than an array $b$ of the same size if and only if the following holds:

• in the first position where $a$ and $b$ differ, the array $a$ has a smaller element than the corresponding element in $b$.

企鹅是文明的生物，它们使用排列进行交流。作为企鹅研究员，布莱克斯莱克斯必须研究它们的交流方式。

对于给定的整数 $n$，考虑数组 $[0, 1, \ldots, 2^n - 1]$ 的所有排列$^{\text{∗}}$ $p$。定义

$$S(p) \;=\; \sum_{i=0}^{2^n-1} \operatorname{popcount}\!\bigl(p_0 \mathbin{\&} p_1 \mathbin{\&} \cdots \mathbin{\&} p_i\bigr),$$

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

若一个排列使得 $S(p)$ 达到最大值，则称其为“神圣排列”。请找出字典序最小$^{\text{†}}$的神圣排列。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 中互不相同的 $n$ 个整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数组中 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

$^{\text{†}}$ 对于两个长度相同的数组 $a$ 和 $b$，当且仅当满足以下条件时，称 $a$ 的字典序小于 $b$：

• 在 $a$ 与 $b$ 第一次出现不同元素的位置上，$a$ 中的对应元素严格小于 $b$ 中的对应元素。

The first line contains a single integer $t$ ($1 \le t \le 16$) — the number of test cases.

Each test case contains a single integer $n$ ($1 \le n \le 16$).

It is guaranteed that the sum of $2^n$ over all test cases does not exceed $2^{16}$.

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

每个测试用例包含一个整数 $n$（$1 \le n \le 16$）。

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

For each test case, output $2^n$ integers $p_0, p_1, \ldots, p_{2^n-1}$ — the required permutation.

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

For the first test case, there are two possible permutations.

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

For the second test case, $S([3, 1, 0, 2]) = 3$ is sacred. There are other permutations $p$ that are sacred, such as $p = [3, 2, 0, 1]$, but those are not lexicographically minimal.

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

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

对于第二个测试用例，$S([3, 1, 0, 2]) = 3$ 是神圣的。存在其他神圣的排列 $p$，例如 $p = [3, 2, 0, 1]$，但这些排列并非字典序最小的。