Problem: You are given an array a consisting of n integers (it is guaranteed that n is even, i.e. divisible by 2). All a_i does not exceed some integer k.

Your task is to replace the minimum number of elements (replacement is the following operation: choose some index i from 1 to n and replace a_i with some integer in range [1; k]) to satisfy the following conditions:

  * after all replacements, all a_i are positive integers not greater than k; 
  * for all i from 1 to n/2 the following equation is true: a_i + a_{n - i + 1} = x, where x should be the same for all n/2 pairs of elements. 



You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains two integers n and k (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ k ≤ 2 ⋅ 10^5) — the length of a and the maximum possible value of some a_i correspondingly. It is guratanteed that n is even (i.e. divisible by 2). The second line of the test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ k), where a_i is the i-th element of a.

It is guaranteed that the sum of n (as well as the sum of k) over all test cases does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5, ∑ k ≤ 2 ⋅ 10^5).

Output

For each test case, print the answer — the minimum number of elements you have to replace in a to satisfy the conditions from the problem statement.

Example

Input


4
4 2
1 2 1 2
4 3
1 2 2 1
8 7
6 1 1 7 6 3 4 6
6 6
5 2 6 1 3 4


Output


0
1
4
2

Solution (in PYTHON):

Solution:

# Author : raj1307 - Raj Singh
# Date   : 01.07.2020

from __future__ import division, print_function

import os,sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def msi(): return map(str,input().strip().split(" "))
def li():  return list(mi())

def dmain():
    sys.setrecursionlimit(100000000)
    threading.stack_size(10240000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import log,sqrt,factorial,pi
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *,threading
#from itertools import permutations
#Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[0] 
def sort2(l):return sorted(l, key=getKey)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(n-r))

def ceil(x,y):
    if x%y==0:
        return x//y
    else:
        return x//y+1

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



def read():
    sys.stdin = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 






def main():
    

    
    for _ in range(ii()):

        
    
        n=ii()
        a=li()
        ans=[]
        cur=0
        f=1
        pos=0
        l=[]
        for i in range(n):
            l.append(a[i])
        l.sort()
      

        
        while pos!=n-1:  # for every mum in thr array
            
            if f==0:   # if fslse directly break out of the loop
                break
         
            cur=l[pos]

            for i in range(n):
                
                if a[i]==cur and pos<=i:

                    if i==pos: # if the eleemnt is already in th req pos
                        break

                    j=i



                    if pos==n-2: #  need to check if we have reached the second last ele 


                        if a[pos]<=a[pos+1]:
                            break

                        X=a[pos-1]
                        Y=a[pos]
                        Z=a[pos+1]

                        a[pos-1]=Z
                        a[pos]=X
                        a[pos+1]=Y
                        ans.append(pos-1)
                        if a[pos-1] <= a[pos] and a[pos] <= a[pos+1]:
                            break

                        flag=0
                        #print(pos,'k')
                        for i in range(pos-1,0,-1):


                            X=a[i-1]
                            Y=a[i]
                            Z=a[i+1]

                            a[i-1]=Z
                            a[i]=X
                            a[i+1]=Y
                            ans.append(i-1)

                            if a[i-1] <= a[i] and a[i] <= a[i+1]:
                                flag=1
                                break




                        if flag==0: 
                            f=0


                        break






                        # 2 2 3 5 4  
                        # 2 2 4 3 5
                        # 2 3 2 4 5
                        # 2 2 3 4 5

                        # 2 3 3 5 4
                        # 2 3 4 3 5





                    while True:

                   


                        if j-pos<=2:
                      
                            X=a[pos]
                            Y=a[pos+1]
                            Z=a[pos+2]
                            if X==cur:
                                break
                            ans.append(pos)

                            if Y==cur:
                                a[pos]=Z
                                a[pos+1]=X
                                a[pos+2]=Y

                            elif Z==cur: 
                                a[pos]=Z
                                a[pos+1]=X
                                a[pos+2]=Y

                        else:
                            ans.append(j-2)


                            X=a[j-2]
                            Y=a[j-1]
                            Z=a[j]  

                            a[j-2]=Z
                            a[j-1]=X
                            a[j]=Y
                            j-=2


     
            pos+=1


        if f==0:
            print(-1)
        else:
            print(len(ans))
            for i in range(len(ans)):
                print(ans[i]+1,end=' ')
            print()













       















# region fastio 
# template taken from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
    #read()
    main()
    #dmain()

# Comment Read()