A permutation of length $n$ is an array $p=[p_1,p_2,\dots,p_n]$, which contains every integer from $1$ to $n$ (inclusive) and, moreover, each number appears exactly once. For example, $p=[3,1,4,2,5]$ is a permutation of length $5$.

For a given number $n$ ($n \ge 2$), find a permutation $p$ in which absolute difference (that is, the absolute value of difference) of any two neighboring (adjacent) elements is between $2$ and $4$, inclusive. Formally, find such permutation $p$ that $2 \le |p_i - p_{i+1}| \le 4$ for each $i$ ($1 \le i < n$).

Print any such permutation for the given integer $n$ or determine that it does not exist.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases in the input. Then $t$ test cases follow.

Each test case is described by a single line containing an integer $n$ ($2 \le n \le 1000$).


-----Output-----

Print $t$ lines. Print a permutation that meets the given requirements. If there are several such permutations, then print any of them. If no such permutation exists, print -1.


-----Example-----
Input
6
10
2
4
6
7
13

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

Difficulty: introductory

Starter code:

Solutions:
T = int(input())
for _ in range(T):
    n = int(input())
    if n <= 3:
        print(-1)
    else:
        left = []
        for i in range(1, n + 1, 2):
            left.append(i)
        right = []
        right.append(4)
        right.append(2)
        for i in range(6, n + 1, 2):
            right.append(i)
        right.reverse()

        for i in left:
            right.append(i)
        
        for i in right:
            print(i, end = " ")
        print("")

t = int(input())
for __ in range(t):
    n = int(input())
    if n <= 3:
        print(-1)
    else:
        ps = [[2,4,1,3],[3,1,4,2,5],[1,4,2,5,3,6],[5,1,3,6,2,4,7]]
        ret = ps[n%4]
        for i in range((n%4) + 4, n, 4):
            ret.extend([i+2,i+4,i+1,i+3])
        print(" ".join(map(str, ret)))

#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        if n == 2 or n == 3:
            print(-1)
            continue
        if n == 4:
            print('3 1 4 2')
            continue
        a = [2 * i + 1 for i in range((n + 1) // 2)]
        a.append(a[-1] - 3)
        if a[-1] + 2 == (n // 2) * 2:
            a.append(a[-1] + 2)
        else:
            a.append(a[-1] + 4)
        b = [2 * i + 2 for i in range(n // 2)]
        b = b[::-1]
        for i in b:
            if i not in a:
                a.append(i)
        print(*a)
    return

def __starting_point():
    main()
__starting_point()

t = int(input())
for aoaoao in range(t):
    n = int(input())
    if n == 1:
        print(1)
    elif n < 5:
    	if n == 4:
    		print("3 1 4 2")
    	else:
	        print(-1)
    else:
        a = [[], [], [], [], []]
        a[0] = [1, 3, 5, 2, 4]
        a[1] = [1, 3, 5, 2, 6, 4]
        a[2] = [1, 3, 5, 7, 4, 2, 6]
        a[3] = [1, 3, 5, 8, 6, 2, 4, 7]
        a[4] = [1, 3, 5, 9, 7, 4, 2, 6, 8]
        f = -1
        for x in a[n % 5]:
            print(x, end = " ")
        f = max(a[n % 5])
        while f < n:
            for x in a[0]:
                print(f + x, end = " ")
            f += 5
        print()
        

def Zs(): return list(map(int, input().split()))
def Z(): return int(input())

def solve(n):
    if n <= 3: return None
    ans = []
    k = 1
    while n >= 8:
        ans.extend([k + 1, k + 3, k, k + 2])
        n -= 4
        k += 4
    if n == 4:
        ans.extend([x + k for x in [2, 0, 3, 1]])
    elif n == 5:
        ans.extend([x + k for x in [2, 0, 4, 1, 3]])
    elif n == 6:
        ans.extend([x + k for x in [2, 0, 4, 1, 3, 5]])
    else:
        ans.extend([x + k for x in [2, 0, 4, 1, 5, 3, 6]])
    return ans

for _ in range(Z()):
    n = Z()
    ans = solve(n)
    if ans is not None:
        print(*ans)
    else:
        print(-1)




for _ in range(int(input())):
	n = int(input())
	if n == 4:
		print(3, 1, 4, 2)
		continue
	if n < 5:
		print(-1)
		continue
	arr = []
	done = [False] * n
	for i in range(0, n, 2):
		arr.append(i)
		done[i] = True
	for i in range(arr[-1]-3, 0, -4):
		arr.append(i)
		done[i] = True
	for i in range(n):
		if not done[i]:
			arr.append(i)

	print(*[e+1 for e in arr])


def solve(l,r):
	n=r-l+1
	#print(l,r,n)
	if n==0:
		return []
	elif n%4==0:
		return [l+1,l+3,l,l+2]+solve(l+4,r)
	elif n%4==1:
		return [l]+solve(l+1,r)
	elif n%4==2:
		return [l]+solve(l+1,r-1)+[r]
	return [5, 1, 3, 6, 2, 4, 7]+solve(l+7,r)
t=int(input())
for i in range(t):
	n=int(input())
	if n<=3:
		print(-1)
	else:
		print(*solve(1,n))

#!/usr/bin/env python3
from sys import stdin
import collections


def solve(tc):
    n = int(stdin.readline().strip())
    if n<4:
        print(-1)
        return
    base = collections.deque()
    base.extend([2,4,1,3])
    p = 5
    while p+1<=n:
        base.append(p)
        base.appendleft(p+1)
        p += 2
    
    if p==n:
        base.append(p)

    for x in base:
        print(x, end=' ')
    print()
    
LOCAL_TEST = not __debug__
if LOCAL_TEST:
    infile = __file__.split('.')[0] + "-test.in"
    stdin = open(infile, 'r')

tcs = int(stdin.readline().strip())
tc = 1
while tc <= tcs:
    solve(tc)
    tc += 1

from sys import stdin
 
for _ in range(int(stdin.readline())):
    inp = int(stdin.readline())
    if inp<4:
        print('-1')
    else:
        odd = list(range(5,inp+1,2))
        odd.reverse()
        even = list(range(6,inp+1,2))
        r = odd+[3,1,4,2]+even
        print(' '.join(map(str,r)))
        


# cook your dish here
t=int(input())
for _ in range(t):
    n=int(input())
    if n==2 or n==3 :
        print(-1)
        #break
    elif n==4:
        print("3 1 4 2")
    else:
        c=1
        if n%2==0:
            for i in range(1,n,2):
                print(i,end=" ")
            if n-4>0:
                print(n-4,end=" ")
            for i in range(n,0,-2):
                if i !=(n-4) and i!=0:
                    print(i,end=" ")
        else:
            for i in range(1,n+1,2):
                print(i,end=" ")
            if n-3>0:
                print(n-3,end=" ")
            for i in range(n-1,0,-2):
                if i!=(n-3) and i!=0:
                    print(i,end=" ")
            
            
        print()
    
        

t = int(input())
for _ in range(t):
    out = []
    works = True
    n = int(input())
    while n:
        if n == 1:
            out.append(1)
            break
        elif n == 2:
            works = False
            break
        elif n == 3:
            works = False
            break
        elif n == 4:
            out += [3, 1, 4, 2]
            break
        elif n == 5:
            out += [5,2,4,1,3]
            break
        elif n == 7:
            out += [7, 4, 2, 6, 3, 1, 5]
            break
        elif n == 8:
            out += [8, 4, 7, 3, 6, 2, 5, 1]
            break
        elif n == 9:
            out += [9, 7, 4, 2, 6, 8, 5, 1, 3]
            break
        else:
            out.append(n)
            out.append(n - 3)
            out.append(n - 1)
            out.append(n - 4)
            out.append(n - 2)
            n -= 5
    if works:
        print(*out)
    else:
        print(-1)
        


t = int( input() )

for i in range( t ):
  n = int( input() )

  if n<=3:
    print( "-1" )
    continue

  ans = [ 2 , 4 , 1 , 3 ]

  m = 4
  idx = 1

  while m < n:
    m = m+1
    ans.append( m )

    m = m+1
    if m<=n:
      idx = 1
      while idx < len( ans ):
        if m-ans[idx-1] >= 2 and m-ans[idx-1]<=4 and m-ans[idx]>=2 and m-ans[idx]<=4:
          break
        idx = idx+1
      ans.insert( idx , m ) 

  for p in ans:
    print( p , end = " " )
  print( "\n" ) 


  

t = int(input())
for i in range(t):
    n=int(input())
    if n==2:
        print(-1)
        continue
    if n==3:
        print(-1)
        continue
    if n==4:
        print(3,1,4,2)
        continue
    if n==5:
        print(1,3,5,2,4)
        continue
    if n%2==0:
        for i in range(n//2):
            print(i*2+1,end=' ')
        print(n - 4, n, n - 2, end=' ')
        for i in range(n//2-3):
            print(n-6-2*i, end=' ')
        print()
    if n%2==1:
        for i in range(n//2+1):
            print(i*2+1,end=' ')
        print(n-3, n-1, end=' ')
        for i in range(n//2-2):
            print(n-5-2*i, end=' ')
        print()
        
    
        

t = int(input())

while t!=0:
    t-=1 
    n = int(input())
    if n==2 or n==3:
        print(-1)
    else:
        odd = [i for i in range(1,n+1,2)]
        eve = [i for i in range(2, n+1,2)]
        odd.reverse()
        eve[0] , eve[1] = eve[1] , eve[0]
        odd+=eve 
        print(*odd)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2 or n == 3:
		print(-1)
		continue
	if n >= 4:
		ans = []
		if n%4 == 0:
			for i in range(1, n+1, 4):
				ans += [i+1, i+3, i, i+2]
		else:
			d = n//4 - 1
			cur = 1
			for i in range(d):
				ans += [cur+1, cur+3, cur, cur+2]
				cur += 4
			if n%4 == 1:
				ans += [cur+1, cur+3, cur, cur+2, cur+4]
			elif n%4 == 2:
				ans += [cur, cur+2, cur+4, cur+1, cur+3, cur+5]
			else:
				ans += [cur, cur+3, cur+1, cur+5, cur+2, cur+4, cur+6]				


		print(*ans)


# HEY STALKER
for _ in range(int(input())):
    n = int(input())
    if n <= 3:
        print(-1)
    else:
        k = []
        for t in range(n, 0, -2):
            k.append(t)
        l = []
        for t in range(n-3, 0, -2):
            l.append(t)
        l.insert(1, n-1)
        l.reverse()
        print(*l, *k)

for _ in range(int(input())):
    n = int(input())
    ar = []
    kek = set()
    for i in range(1, n + 1):
        kek.add(i)
    kek.discard(n - 1)
    ar.append(n - 1)
    for i in range(n):
        if ar[-1] - 3 in kek:
            kek.discard(ar[-1] - 3)
            ar.append(ar[-1] - 3)
        elif ar[-1] - 2 in kek:
            kek.discard(ar[-1] - 2)
            ar.append(ar[-1] - 2)
        elif ar[-1] - 4 in kek:
            kek.discard(ar[-1] - 4)
            ar.append(ar[-1] - 4)
        elif ar[-1] + 3 in kek:
            kek.discard(ar[-1] + 3)
            ar.append(ar[-1] + 3)
        elif ar[-1] + 2 in kek:
            kek.discard(ar[-1] + 2)
            ar.append(ar[-1] + 2)
        elif ar[-1] + 4 in kek:
            kek.discard(ar[-1] + 4)
            ar.append(ar[-1] + 4)
    if n == 2 or n == 3 or n == 1:
        print(-1)
    else:
        print(*ar)