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: interview

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)
 

# cook your dish here
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=""
 #print(log2(n))
 if n>1 and log2(n)==int(log2(n)):
  print(-1)
 else:
  #print(3)
  f=[0]*n
  s=n//2
  if n==1:
   s=1
  f[s-1]=1
  s1+="{} ".format(s)
  #print(s1)
  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(f,"000000000000")
   #(f)    
  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
 # print(k)
 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:]
 # return ans


for _ in range(int(input())):
 n = int(input())
 # n,k = [int(j) for j in input().split()]
 # a = [int(j) for j in input().split()]
 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)
 else:
  if 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() 
 

import math
t=int(input())
for _ in range(t):
 n=int(input())
 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() 

# cook your dish here
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)

# cook your dish here
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)
   else:
    if 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
testcases=int(input())
while(testcases>=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")
  testcases-=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(testcases>=2):
  print()
 testcases-=1
  




import math
testcases=int(input())
while(testcases>=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")
  testcases-=1
  continue
 elif 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(testcases>=2):
  print()
 testcases-=1



import math
testcases=int(input())
while(testcases>=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')
  testcases-=1
  continue
 elif 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(testcases>=2):
  print()
 testcases-=1



import math
for x in range(int(input())):
 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
 elif N==1:
  print('1')
 elif(N==3):
  print("2 3 1")
 elif(N==5):
  print("2 3 1 5 4")
 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
for x in range(int(input())):
 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
 elif N==1:
  print('1')
 elif(N==3):
  print("2 3 1")
 elif(N==5):
  print("2 3 1 5 4")
 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
for x in range(int(input())):
 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
 elif N==1:
  print(1)
 elif(N==3):
  print("2 3 1")
 elif(N==5):
  print("2 3 1 5 4")
 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


  

# cook your dish here
import math
for x in range(int(input())):
 N=int(input())
 permutations=list()
 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
 elif N==1:
  print('1')
 elif(N==3):
  print("2 3 1")
 elif(N==5):
  print("2 3 1 5 4")
 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(' ')