题目描述

求字典序最小的序列 $p_0, p_1, p_2 \cdots, p_{n-1}$，该序列是 $0, 1, 2, \cdots, (n - 1)$ 的一个排列，且满足以下限制：对于所有 $0 \le i < n$，都有 $p_0 \oplus p_1 \oplus \cdots \oplus p_i > 0$。这里 $\oplus$ 是按位异或运算。

称一个长度为 $n$ 的序列 $p_0, p_1, \cdots, p_{n - 1}$ 的字典序小于另一个长度为 $n$ 的序列 $q_0, q_1, \cdots, q_{n - 1}$，若存在一个整数 $0 \le k < n$ 使得对于所有 $0 \le i < k$ 有 $p_i = q_i$，以及 $p_k < q_k$。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 10^6$）。

保证所有数据 $n$ 之和不超过 $10^6$。

输出格式

每组数据输出一行 $n$ 个由单个空格分隔的整数，表示字典序最小的且满足限制的排列。如果不存在这种排列，输出 $\texttt{impossible}$。

4
1
2
3
4

impossible
1 0
1 0 2
impossible