A permutation $p_1,p_2...p_N$ of $\{1, 2, ..., N\}$ is beautiful if $p_i \& p_{i+1}$ is greater than 0 for every $1 \leq i < N$ . You are given an integer $N$, and your task is toconstruct a beautiful permutation of length $N$ or determine that it's impossible.
Note that $a \& b$ denotes the bitwise AND of $a$ and $b$.

-----Input:-----
First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains a single line of input, an integer $N$.

-----Output:-----
For each test case output $-1$ if there is no suitable permutation of length $N$, otherwise output $N$ integers in a single line which form a beautiful permutation. If there are multiple answers output any of them.

-----Constraints-----
- $1 \leq N \leq 10^5$
- The sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
- 50 points : $1 \leq N,T \leq 9$
- 50 points : Original constraints

-----Sample Input:-----
3
4
3
5

-----Sample Output:-----
-1
1 3 2
2 3 1 5 4

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import math

def ispoweroftwo(y):
	return math.ceil(math.log(y, 2)) == math.floor(math.log(y, 2))
t = int(input())
for i in range(t):
	n = int(input())
	a = []
	if ispoweroftwo(n) and n != 1:
		print(-1, end=' ')
	if n == 1:
		print(1)
	if n >= 3 and (not ispoweroftwo(n)):
		a.append(2)
		a.append(3)
		a.append(1)
	if n > 3 and (not ispoweroftwo(n)):
		i = 4
		while i <= n:
			if ispoweroftwo(i):
				a.append(i + 1)
				a.append(i)
				i += 2
			else:
				a.append(i)
				i += 1
	print(*a)


import math

def isPowerOfTwo(y):
	return math.ceil(math.log(y, 2)) == math.floor(math.log(y, 2))
test = int(input())
for _ in range(test):
	n = int(input())
	a = []
	if n == 1:
		a.append(1)
	if isPowerOfTwo(n) and n != 1:
		print('-1')
	if n >= 3 and (not isPowerOfTwo(n)):
		a.append(2)
		a.append(3)
		a.append(1)
	if n > 3 and (not isPowerOfTwo(n)):
		i = 4
		while i <= n:
			if isPowerOfTwo(i):
				a.append(i + 1)
				a.append(i)
				i = i + 2
			else:
				a.append(i)
				i = i + 1
	print(*a)


from math import log2
t = int(input())
for _ in range(t):
	n = int(input())
	s1 = ''
	if n > 1 and log2(n) == int(log2(n)):
		print(-1)
	else:
		f = [0] * n
		s = n // 2
		if n == 1:
			s = 1
		f[s - 1] = 1
		s1 += '{} '.format(s)
		while f != [1] * n:
			for i in range(n):
				if f[i] == 0 and s & i + 1 > 0:
					s = i + 1
					s1 += '{} '.format(s)
					f[s - 1] = 1
					break
		print(s1)


import math

def isPowerOfTwo(y):
	return math.ceil(math.log(y, 2)) == math.floor(math.log(y, 2))
t = int(input())
while t != 0:
	n = int(input())
	a = []
	if n == 1:
		a.append(1)
	if isPowerOfTwo(n) and n != 1:
		print('-1')
	if n >= 3 and (not isPowerOfTwo(n)):
		a.append(2)
		a.append(3)
		a.append(1)
	if n > 3 and (not isPowerOfTwo(n)):
		i = 4
		while i <= n:
			if isPowerOfTwo(i):
				a.append(i + 1)
				a.append(i)
				i = i + 2
			else:
				a.append(i)
				i = i + 1
	print(*a)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(1)
	elif n & n - 1 == 0:
		print(-1)
	else:
		v = [2, 3, 1]
		for i in range(4, n + 1):
			v.append(i)
		for i in range(3, n):
			if v[i] & v[i - 1] == 0:
				(v[i], v[i + 1]) = (v[i + 1], v[i])
		for i in range(len(v)):
			print(v[i], end=' ')
		print()


def func(n):
	k = n
	if k == 1:
		return [1]
	while k % 2 == 0:
		k = k // 2
	if k == 1:
		return -1
	ans = [i for i in range(1, n + 1)]
	i = 2
	while i < n:
		(ans[i - 1], ans[i]) = (ans[i], ans[i - 1])
		i *= 2
	if n < 4:
		return ans
	return [2, 3, 1, 5, 4] + ans[5:]
for _ in range(int(input())):
	n = int(input())
	ans = func(n)
	if type(ans) == int:
		print(-1)
	else:
		print(*ans)


import math
for _ in range(int(input())):
	n = int(input())
	a = []
	b = [2, 3, 1, 5, 4]
	for i in range(18):
		a.append(i)
	t = math.log(n, 2)
	if t in a:
		print(-1)
	elif n == 3:
		print(1, 3, 2)
	elif n == 5:
		print(2, 3, 1, 5, 4)
	else:
		for i in range(6, n + 1):
			b.append(i)
		i = 5
		while i < n:
			t1 = math.log(b[i], 2)
			if t1 in a:
				(b[i], b[i + 1]) = (b[i + 1], b[i])
				if i == n - 2:
					break
				else:
					i += 1
			i += 1
		print(*b)


def powerf(P):
	return P != 0 and P & P - 1 == 0
test = int(input())
for i in range(test):
	N = int(input())
	if N == 1:
		print(N)
		continue
	elif N == 3:
		print(1, 3, 2)
		continue
	elif N == 5:
		print(2, 3, 1, 5, 4)
	elif powerf(N):
		print(-1)
		continue
	else:
		print(2, 3, 1, 5, 4)
		i = 6
		while i <= N:
			if powerf(i):
				print(i + 1, i)
				i = i + 2
			else:
				print(i)
				i = i + 1


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
		continue
	k = math.log(n, 2)
	if k == int(k):
		print(-1)
	else:
		li = [x + 1 for x in range(n)]
		(li[0], li[1], li[2]) = (2, 3, 1)
		i = 3
		while i < n:
			if li[i] != 2:
				m = math.log(li[i], 2)
				if m == int(m):
					(li[i], li[i + 1]) = (li[i + 1], li[i])
					i += 1
			i += 1
		for i in range(n):
			print(li[i], end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	elif n & n - 1 == 0:
		print(-1)
	elif n == 3:
		print(*[1, 3, 2])
	elif n == 5:
		print(*[2, 3, 1, 5, 4])
	elif n >= 6:
		res = [1, 3, 2, 6, 4, 5] + list(range(7, n + 1))
		start = 8
		while start < n:
			(res[start - 1], res[start]) = (res[start], res[start - 1])
			start *= 2
		print(*res)


ml = [2 ** i for i in range(18)]
ml1 = [2 ** i + 1 for i in range(18)]
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	if n in ml:
		print(-1)
		continue
	l = [2, 3, 1]
	l2 = []
	i = n
	while i > 3:
		if i in ml1:
			l2 += [i - 1, i]
			i -= 1
		else:
			l2.append(i)
		i -= 1
	print(*l + l2[::-1])


import math
for i in range(int(input())):
	l = [2, 3, 1]
	num = int(input())
	if math.ceil(math.log2(num)) == math.floor(math.log2(num)):
		print(-1)
		continue
	elif num == 1:
		print(1)
		continue
	elif num == 3:
		print('1 3 2')
		continue
	else:
		for i in range(4, num + 1):
			if math.ceil(math.log2(i)) == math.floor(math.log2(i)):
				if i not in l:
					l.append(i + 1)
					l.append(i)
			elif i not in l:
				l.append(i)
	print(' '.join(map(str, l)))


import math
testcases = int(input())
for x in range(testcases):
	N = int(input())
	l = 6
	m = 3
	a = 2 ** m
	if N != 1 and math.ceil(math.log(N, 2)) == math.floor(math.log(N, 2)):
		print('-1')
		continue
	if N == 1:
		print('1', end=' ')
	elif N == 3:
		print('2 3 1', end=' ')
	elif N == 5:
		print('2 3 1 5 4', end=' ')
	if N > 5:
		print('2 3 1 5 4', end=' ')
		while l <= N:
			if l == a:
				m = m + 1
				a = 2 ** m
				print(l + 1, end=' ')
				print(l, end=' ')
				l = l + 2
			else:
				print(l, end=' ')
				l = l + 1
	print()


import math
t = int(input())
while t >= 1:
	n = int(input())
	l = 6
	m = 3
	a = 2 ** m
	if n != 1 and math.ceil(math.log(n, 2)) == math.floor(math.log(n, 2)):
		print('-1')
		t = t - 1
		continue
	if n == 1:
		print('1', end=' ')
	elif n == 3:
		print('2 3 1', end=' ')
	elif n == 5:
		print('2 3 1 5 4', end=' ')
	if n > 5:
		print('2 3 1 5 4', end=' ')
		while l <= n:
			if l == a:
				m = m + 1
				a = 2 ** m
				print(l + 1, end=' ')
				print(l, end=' ')
				l = l + 2
			else:
				print(l, end=' ')
				l = l + 1
	if t >= 2:
		print()
	t = t - 1