著名的旅行者 BaoBao 正在访问梦幻王国。梦幻王国中有 $n$ 座城市，编号从 $1$ 到 $n$。这些城市之间由有向道路连接。对于所有 $1 \le i \le n$：

• 如果 $1 \le i - 1 \le n$，则存在一条从第 $i$ 座城市到第 $(i - 1)$ 座城市的道路。
• 如果 $1 \le 2i \le n$，则存在一条从第 $i$ 座城市到第 $2i$ 座城市的道路。
• 如果 $1 \le 2i + 1 \le n$，则存在一条从第 $i$ 座城市到第 $(2i + 1)$ 座城市的道路。
• 如果 $1 \le \lfloor \frac{i}{2} \rfloor \le n$，则存在一条从第 $i$ 座城市到第 $\lfloor \frac{i}{2} \rfloor$ 座城市的道路，其中 $\lfloor \frac{i}{2} \rfloor$ 表示满足 $2x \le i$ 的最大整数 $x$。

BaoBao 从第 $1$ 座城市开始他的旅行。由于他不喜欢重复访问同一座城市，他想找到一条恰好经过每座城市一次的路径。你能帮他找到这样一条路径吗？

输入格式

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

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示梦幻王国中城市的数量。

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

输出格式

对于每组测试数据，输出一行。如果存在一条从第 $1$ 座城市出发并恰好访问每座城市一次的路径，输出 $n$ 个整数 $c_1, c_2, \dots, c_n$，中间用空格隔开，其中 $c_i$ 表示路径中的第 $i$ 座城市（注意根据题目描述，必须满足 $c_1 = 1$）。如果不存在有效的路径，则输出 “-1”（不含引号）。如果存在多个有效答案，输出其中任意一个即可。

请注意，不要在每行末尾输出多余的空格，否则你的答案可能会被判定为错误！

样例

输入 1

2
2
9

输出 1

1 2
1 3 6 5 2 4 9 8 7