Chef has received a challenge for which he needs your help. 

Given N, find a *permutation* P of numbers (1, 2, \ldots, N) such that:  

P_{i} \oplus P_{i+1} \neq P_{i+2} \text{ , where } (1 ≤ i ≤ N-2). Here \oplus denotes the [bitwise XOR] operation.

If multiple such permutations exist, print any. If no such permutation exists, print -1.

Note that, a *permutation* of length N is a sequence of N integers P = (P_{1}, P_{2}, \ldots, P_{N}) such that every integer from 1 to N (inclusive) appears in it exactly once. For example, (2,5,4,1,3) is a permutation of length 5 while (2, 5, 2, 1, 3) is not.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single integer as input, N - the length of the required permutation.

------ Output Format ------ 

For each test case, output in a new line, N space-separated integers, denoting a *permutation* satisfying the condition.  
If multiple such permutations exist, print any. If no such permutation exists, print -1.

------ Constraints ------ 

$1 ≤ T ≤ 500$
$3 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
3
5
10
22
----- Sample Output 1 ------ 
-1
5 1 2 4 3
1 2 4 3 6 10 8 9 7 5
10 9 8 7 6 5 1 2 4 3 11 12 13 14 15 16 17 18 19 20 21 22

----- explanation 1 ------ 
Test Case $1$: There is no permutation that satisfies the given XOR condition.

Test Case $2$: $ (5 \oplus 1 = 4) \text{ ,   } (1 \oplus 2 = 3) \text{ ,   } (2 \oplus 4 = 6) $  
Since all the adjacent XORs are different from the next term, hence, this is a valid answer.

Test Case $3$: $ (1 \oplus 2 = 3) \text{ ,   } (2 \oplus 4 = 6) \text{ ,   } (4 \oplus 3 = 7) \text{  and so on... } $  
Since all the adjacent XORs are different from the next term, hence, this is a valid answer.

Test Case $4$: $ (10 \oplus 9 = 3) \text{ ,   } (9 \oplus 8 = 1) \text{ ,   } (8 \oplus 7 = 15) \text{  and so on... } $  
Since all the adjacent XORs are different from the next term, hence, this is a valid answer.

Difficulty: MEDIUM
Tags: Constructive algorithms

Starter code:

Solutions:
T = int(input())
for _ in range(0, T):
	N = int(input())
	if N == 3:
		print('-1')
	elif N == 4:
		print('5 1 2 4 3')
	else:
		to_print = '5 1 2 4 3'
		for i in range(6, N + 1):
			to_print += ' {}'.format(i)
		print(to_print)


def solve():
	n = int(input())
	if n == 3:
		print('-1')
	elif n == 4:
		print('1 2 4 3')
	else:
		print('5 1 2 4 3', end=' ')
		if n > 5:
			for i in range(6, n + 1):
				print(i, end=' ')
		print()
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = [1, 2, 4, 3]
	if n == 3:
		print(-1)
		continue
	else:
		for i in range(5, n + 1):
			a.insert(0, i)
		print(*a)


for forbid in range(int(input())):
	num = int(input())
	if num == 3:
		print(-1, end='')
	else:
		print(3, 1, 4, 2, end=' ')
		for i in range(num - 4):
			print(5 + i, end=' ')
	print()


tests = int(input())
for i in range(tests):
	num = int(input())
	if num == 3:
		print(-1)
	else:
		ans = [1, num]
		for j in range(2, num):
			ans.append(j)
		print(*ans)


for i in range(int(input())):
	n = int(input())
	if n <= 3:
		print(-1)
	else:
		for i in range(3, n + 1):
			print(i, end=' ')
		print(2, 1)


for i in range(int(input())):
	n = int(input())
	k = []
	if n != 3:
		for i in range(n, 4, -1):
			k.append(i)
		k.append(1)
		k.append(2)
		k.append(4)
		k.append(3)
		print(*k)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 3:
		print(-1)
	elif n % 2 != 0:
		for i in range(n, n // 2 - 1, -2):
			print(i, end=' ')
		cnt = 2
		if i + 2 ^ i == 2:
			print('4 2', end=' ')
		else:
			print('2 4', end=' ')
		print(1, end=' ')
		for i in range(6, n, 2):
			print(i, end=' ')
			cnt += 1
			if cnt % 2 == 0:
				print(cnt - 1, end=' ')
		print()
	else:
		for i in range(n - 1, n // 2 - 1, -2):
			print(i, end=' ')
		cnt = 2
		if i + 2 ^ i == 2:
			print('4 2', end=' ')
		else:
			print('2 4', end=' ')
		print(1, end=' ')
		for i in range(6, n + 1, 2):
			print(i, end=' ')
			cnt += 1
			if cnt % 2 == 0:
				print(cnt - 1, end=' ')
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 3:
		print(-1)
	else:
		print('1 3 4 2', end=' ')
		for i in range(5, n + 1):
			print(i, end=' ')
		print()


case = int(input())
for i in range(case):
	n = int(input())
	if n == 3:
		print(-1)
	else:
		print(1, 3, 4, 2, end=' ')
		for i in range(5, n + 1):
			print(i, end=' ')
		print()


def ans(n):
	arr = [1, 2, 4, 3]
	if n == 3:
		return [-1]
	else:
		k = []
		while n != 4:
			k.append(n)
			n -= 1
		for y in arr:
			k.append(y)
		return k
test_cases = int(input())
while test_cases != 0:
	d = int(input())
	print(*ans(d))
	test_cases -= 1


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n == 3:
		print(-1)
		continue
	for i in range(1, n + 1):
		if i != 2:
			print(i, end=' ')
	print(2)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n == 3:
		print('-1')
		continue
	a = [None] * n
	a[0] = 1
	a[1] = 2
	i = 2
	while i < n:
		if i == 2 or i == 5:
			a[i] = i + 2
			if i + 1 < n:
				a[i + 1] = i + 1
			i = i + 2
		else:
			a[i] = i + 1
			i = i + 1
	for i in range(n):
		print(a[i], end=' ')
	print()


t = int(input())
while t:
	n = int(input())
	if n == 3:
		print('-1')
	else:
		li = [1, 3, 4, 2]
		i = 5
		while i <= n:
			li.append(i)
			i += 1
		for el in li:
			print(el, end=' ')
		print()
	t -= 1


testcases = int(input())
for eachcase in range(testcases):
	limit = int(input())
	if limit == 3:
		print(-1)
	else:
		print(1, 3, 4, 2, end=' ')
		if limit > 4:
			for numbers in range(5, limit + 1):
				print(numbers, end=' ')
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print('1 2')
	elif n == 3:
		print(-1)
	else:
		print('1 2 ', end='')
		for i in range(n, 2, -1):
			print(i, end=' ')
		print()


def solve():
	n = int(input())
	a = []
	if n == 3:
		return -1
	else:
		for i in range(5, n + 1):
			a.append(str(i))
	ans = '1 3 4 2 '
	for j in range(0, len(a)):
		ans += a[j] + ' '
	return ans
t = int(input())
for i in range(0, t):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	l = [1, 3, 4, 2]
	if n == 3:
		print(-1)
	else:
		for i in range(5, n + 1):
			l.append(i)
		print(*l)


test_cases = int(input())
for t in range(test_cases):
	n = int(input())
	if n <= 3:
		print(-1)
		continue
	res = [i for i in range(1, n + 1)]
	res[1] = 3
	res[2] = 4
	res[3] = 2
	print(*res)


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	if n == 3:
		print(-1)
	else:
		k = 1
		while k != n + 1:
			if k == 1:
				l.append(1)
			elif k == 2:
				l.append(3)
			elif k == 3:
				l.append(4)
			elif k == 4:
				l.append(2)
			else:
				l.append(k)
			k += 1
	print(' '.join((str(x) for x in l)))


t = int(input())
for tt in range(t):
	n = int(input())
	if n == 3:
		print(-1)
	elif n == 2:
		print(1, 2)
	elif n == 1:
		print(1)
	else:
		ls = [1, 3, 4, 2]
		for i in range(n - 4):
			ls.append(i + 5)
		for j in range(n):
			print(ls[j], end=' ')
	print()


import sys
from os import path
from math import gcd
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = int(input())
	seq = []
	if n == 3:
		print(-1)
		continue
	seq = [i for i in range(n, 0, -1)]
	seq[-4] = 2
	seq[-3] = 4
	seq[-2] = 3
	for i in seq:
		print(i, end=' ')
	print()


for i in range(int(input())):
	N = int(input())
	if N == 3:
		print(-1)
	else:
		print(1, N, N - 2, N - 1, end=' ')
		k = N - 3
		while k > 1:
			print(k, end=' ')
			k -= 1
		print()


for _ in range(int(input())):
	n = int(input())
	a = [i + 1 for i in range(n)]
	if n == 3:
		print(-1)
	else:
		(a[1], a[2]) = (a[2], a[1])
		(a[2], a[3]) = (a[3], a[2])
		print(*a)


ans = [1, 2, 4, 3]
for t in range(int(input())):
	n = int(input())
	if n == 3:
		print(-1)
	else:
		suf = list(range(5, n + 1, 2))
		pref = list(range(6, n + 1, 2))
		print(' '.join(map(str, pref[::-1] + ans + suf)))


t = int(input())
while t > 0:
	n = int(input())
	if n < 4:
		print(-1)
	else:
		ans = '1 3 4 2 '
		for i in range(5, n + 1):
			ans += str(i) + ' '
		print(ans)
	t -= 1


def check(A):
	N = len(A)
	for i in range(N - 2):
		if A[i] ^ A[i + 1] ^ A[i + 2] == 0:
			print(f'Error in {N} {i}')
			print(A)
	return

def solve(N):
	if N == 3:
		return [-1]
	ret = [1, N] + list(range(2, N))
	check(ret)
	return ret

def main():
	T = int(input())
	for i in range(T):
		N = int(input())
		print(*solve(N))
main()


ans = ''
for _ in range(int(input())):
	n = int(input())
	res = '1 2 '
	(l1, l2) = (1, 2)
	i = 3
	j = n
	while i <= j:
		if l1 ^ l2 != i and i <= j:
			res += str(i) + ' '
			(l1, l2) = (l2, i)
			i += 1
		elif l1 ^ l2 != j and i <= j:
			res += str(j) + ' '
			(l1, l2) = (l2, j)
			j -= 1
		else:
			res = '-1'
			break
	ans += res + '\n'
print(ans)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n == 3:
		print(-1)
	else:
		print(1, 3, end=' ')
		for i in range(4, n + 1):
			print(i, end=' ')
		print(2)


t = int(input())
for i in range(t):
	n = int(input())
	l = [1, 3, 4, 2]
	if n == 3:
		print(-1)
	else:
		for i in range(5, n + 1):
			l.append(i)
		l = list(map(str, l))
		print(' '.join(l))


fptr = open(0)
for _ in range(int(next(fptr))):
	N = int(next(fptr))
	a = [1, 3, 4, 2]
	if N == 3:
		print(-1)
	elif N == 4:
		print(1, 3, 4, 2)
	else:
		for i in range(N):
			if i < 4:
				print(a[i], end=' ')
			elif i != N - 1:
				print(i + 1, end=' ')
			else:
				print(N)


for _ in range(int(input())):
	N = int(input())
	a = [1, 3, 4, 2]
	if N == 3:
		print(-1)
	elif N == 4:
		print(1, 3, 4, 2)
	else:
		for i in range(N):
			if i < 4:
				print(a[i], end=' ')
			elif i != N - 1:
				print(i + 1, end=' ')
			else:
				print(N)


t = int(input())
while t > 0:
	num = int(input())
	if num == 3:
		print(-1)
	else:
		print(1, num, num - 2, num - 1, end=' ')
		k = num - 3
		while k > 1:
			print(k, end=' ')
			k -= 1
		print()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	if n == 3:
		print(-1)
		continue
	ans = []
	for i in range(1, n + 1):
		if i != 2:
			ans.append(i)
	ans.append(2)
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	ans = [1, 3, 4, 2]
	if n == 3:
		print('-1')
	else:
		for i in range(4, n):
			ans.append(i + 1)
		print(*ans)


t = int(input())
for x in range(t):
	n = int(input())
	if n == 3:
		print(-1, end=' ')
	else:
		print('1 3 4 2', end=' ')
		n += 1
		for k in range(5, n):
			print(str(k), end=' ')
	print()


def xor_perm(n):
	if n <= 3:
		return [-1]
	base = [3, 4, 2, 1]
	i = 5
	while i <= n:
		base.append(i)
		i += 1
	return base[::-1]
for _ in range(int(input())):
	n = int(input())
	print(*xor_perm(n))


for _ in range(int(input())):
	n = int(input())
	l = ['1', '3', '4', '2']
	if n == 1:
		print(1)
	if n == 2:
		print('1', '2')
	if n == 3:
		print(-1)
	elif n <= len(l):
		print(' '.join(l[:n]))
	else:
		for i in range(5, n + 1):
			l.append(str(i))
		print(' '.join(l))


for _ in range(int(input())):
	n = int(input())
	if n == 3:
		print(-1)
	else:
		lis = [2]
		for i in range(n, 2, -1):
			lis.append(i)
		lis.append(1)
		print(*lis)


for i in range(int(input())):
	n = int(input())
	if n == 3:
		print(-1)
	else:
		l = [2]
		for i in range(n, 2, -1):
			l.append(i)
		l.append(1)
		print(*l)


def solve():
	n = int(input())
	arr = [1, 2, 4, 3, 5, 7, 6]
	if n == 3:
		return -1
	if n <= 7:
		return arr[:n]
	else:
		for i in range(8, n + 1):
			arr.append(i)
		return arr
for _ in range(int(input())):
	a = solve()
	if a == -1:
		print(-1)
	else:
		for i in a:
			print(i, end=' ')
		print('')


import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7

def solve():
	n = int(input())
	if n <= 3:
		return [-1]
	return [*range(5, n + 1)] + [2, 3, 4, 1]
for _ in range(int(input())):
	print(*solve())


def xor(n):
	if n == 3:
		print(-1)
		return
	arr = [1, 2, 4, 3]
	for i in range(5, n + 1):
		if i == 5:
			arr = [5] + arr
		else:
			arr.append(i)
	for e in arr:
		print(e, end=' ')
	print('', end='\n')
t = int(input())
for i in range(t):
	n = int(input())
	xor(n)


n = int(input())
while n:
	n -= 1
	i = int(input())
	if i < 4:
		print(-1)
		continue
	arr = [x for x in range(3, 1 + i)]
	arr = [1] + arr + [2]
	print(' '.join((str(x) for x in arr)))


for _ in range(int(input())):
	n = int(input())
	if n == 3:
		print(-1)
	if n == 4:
		print(1, 2, 4, 3)
	if n == 5:
		print(5, 1, 2, 4, 3)
	if n == 6:
		print(6, 5, 1, 2, 4, 3)
	if n == 7:
		print(7, 6, 5, 1, 2, 4, 3)
	elif n >= 8:
		powers = [1, 2, 4, 5, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536]
		ans = []
		ind = 0
		for i in range(1, n + 1):
			if i in powers or i == 5:
				ind += 1
				continue
			ans.append(i)
		ans.extend(powers[1:ind])
		ans.append(1)
		print(*ans)
		if len(set(ans)) != n:
			print(True)
		for i in range(2, len(ans)):
			if ans[i - 2] ^ ans[i - 1] == ans[i]:
				print(i)
				print(True)


def solve(n):
	if n == 3:
		return '-1'
	ans = list(range(3, n + 1)) + [2, 1]
	return ' '.join(list(map(str, ans)))

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		res = solve(n)
		print(res)
main()


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		ans = []
		for i in range(2, n + 1):
			ans.append(i)
		ans.append(1)
		for i in ans:
			print(i, end=' ')
		print()
	else:
		if n == 3:
			print(-1)
			continue
		ans = []
		for i in range(2, n):
			ans.append(i)
		ans = [1] + [n] + ans
		for i in ans:
			print(i, end=' ')
		print()


for i in range(int(input())):
	num = int(input())
	ans = []
	i = 3
	j = num
	while i <= j:
		ans.append(i)
		i += 1
	ans.append(2)
	ans.append(1)
	if num == 3:
		print(-1)
	elif num == 4:
		print(*[1, 2, 4, 3])
	else:
		print(*ans)


for _ in range(int(input())):
	n = int(input())
	if n == 3:
		print(-1)
	if n >= 4:
		print('1 3 4 2 ', end='')
		if n > 4:
			print(*list(range(5, n + 1)))


def main():
	for _ in range(int(input())):
		N = int(input())
		if N == 3:
			print(-1)
			continue
		arr = list(range(1, N + 1))
		(arr[1], arr[3]) = (arr[3], arr[1])
		print(*arr)
main()


t = int(input())
while t > 0:
	n = int(input())
	if n == 3:
		print(-1)
	else:
		even_counter = 2
		odd_counter = 1
		final_arr = []
		i = 0
		while even_counter <= n:
			if i == 0:
				final_arr.append(odd_counter)
				final_arr.append(even_counter)
				odd_counter += 2
				even_counter += 2
			elif i % 2 == 0 and i != 0:
				final_arr.append(even_counter)
				even_counter += 2
			else:
				final_arr.append(even_counter)
				final_arr.append(odd_counter)
				odd_counter += 2
				even_counter += 2
			i += 1
		while odd_counter <= n:
			final_arr.insert(0, odd_counter)
			odd_counter += 2
		print(*final_arr)
	t -= 1


import sys
import os
import math
import collections
T = int(input())
for _ in range(T):
	N = int(input())
	if N < 4:
		print(-1)
	elif N == 4:
		print(1, 2, 4, 3)
	else:
		print(5, 1, 2, 4, 3, end=' ')
		for i in range(6, N + 1):
			print(i, end=' ')
		print()