1373: 一群龙家军路过

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Special Judger Creator:
Submit:57 Solved:21

Description


「国祚尚为龙,天子尚姓奶,岂有妄为之理?」

奶龙看到还有人替他说话,在天上很欣慰,但是水豚噜噜超级无敌生气暴怒,向奶龙发出了打架邀请。奶龙为了让这只狂妄的水豚退位,假扮奶猪来假扮粉豚噜噜,诱惑水豚噜噜,当场被抓包,导致奶猪奶设崩塌;插上假喙,假扮奶鸡,见人就啄,导致奶鸡被放逐;雇佣私人侦探,制造奶蛇桃色新闻……真是无所不用其极,当真是一条狠毒的龙。这天,奶龙集结了 $n$ 只家龙,组成强悍的龙家军向水豚宣战,这 $n$ 只家龙的战斗力互不相同,恰好构成了 $1$ 到 $n$ 的一个排列。为了发挥出最强实力,奶龙命令他们排成一字长蛇阵,站位索引从 $1$ 开始计。

  • 下标为奇数位置的家龙负责正面硬刚噜噜的嘴炮,这群家龙的奶度定义为他们战斗力的最大公约数。
  • 下标为偶数位置的家龙负责侧翼输出,这群家龙的龙度定义为他们战斗力的按位异或和。

只有当龙家军阵列的奶度和龙度达到完美的平衡时,才能触发「奶龙压顶」击败水豚噜噜。作为奶派忠实的一员,请你帮助奶龙排龙布阵,构造出一个符合条件的龙家军阵列。

也就是说,给定一个整数 $n$,请构造一个 $1$ 到 $n$ 的排列 $p^\dagger$,使得奇数下标位置上的所有元素的最大公约数,等于偶数下标位置上的所有元素的按位异或和 $^{\ast}$。


形式化地,构造一个 $1$ 到 $n$ 的排列 $p_1,p_2,\dots,p_n$,满足:

$$\displaystyle \gcd_{\substack{1 \le i \le n \\[3pt] i \text{ 为奇数}}}p_i = \displaystyle \bigoplus_{\substack{1 \le j \le n \\[3pt] j \text{ 为偶数}}}p_j$$


$^\dagger$ 一个 $1$ 到 $n$ 的排列是指一个由 $n$ 个不同整数组成的序列,其中每个整数都在 $1$ 到 $n$ 之间;换句话说,$1$ 到 $n$ 的每个整数恰好出现一次。

$^\ast$ 按位异或运算 $\oplus$ 对两个整数的二进制每一位分别进行运算:当且仅当两个对应二进制位不同时,该位的结果为 $1$,否则为 $0$。多个整数的按位异或和表示将它们依次异或。

Input

第一行包含一个整数 $T$,表示测试用例的数量。

接下来 $T$ 行,每行一个整数 $n$ $(2 \leq n \leq 2\cdot10^5)$,表示排列的长度。

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

Output

对于每组测试用例,输出一行。

如果能构造出符合条件的排列,输出 $n$ 个整数,表示你构造出的排列 $p$。若存在多个合法排列,输出任意一个即可。若无法构造出任意一个合法排列,请输出 -1

Sample Input Copy

4
2
3
5
14

Sample Output Copy

-1
2 1 3
1 2 4 3 5
1 3 2 4 5 6 7 8 12 9 13 10 14 11

HINT

对于第 $1$ 组数据,只有两个可能的排列为 $[1, 2]$ 或 $[2, 1]$,显然都不合法。

对于第 $3$ 组数据,奇数下标位置上的数字的最大公约数 $\gcd(1, 4, 5) = 1$,偶数下标位置上的数字的按位异或和 $2 \oplus 3 = 1$。