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 PYTHON3):

Solution:
import os
import sys
from io import BytesIO, IOBase

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")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input(): return sys.stdin.readline().rstrip("\r\n")

import traceback

for T in range(int(input())):
    n = int(input())
    d = {}
    prev = {}
    li = [int(i)*501 for i in input().split(' ')]
    #print(len(li))
    sol = False
    invs = 0
    for p,i in enumerate(li):
        if i in d:
            li[p]+=d[i]
            if not sol:
                sol = True
                tar1 = prev[i]
                tar2 = p
                
        d[i] = 1+d.get(i,0)
        prev[i] = p
        for k,v in d.items():
            if k > i:
                invs += v
    if invs&1 and sol == False:
        print(-1)
        continue
    if invs == 0:
        print(0)
        print()
        continue
    ansQ = []
    ans = 0
    c = False
    if sol and invs&1:
        li[tar1],li[tar2] = li[tar2],li[tar1]

    il = sorted(li)
    # print(il)
    # print(li)
    try:
        for p,i in enumerate(il):
            if il[p]!=li[p]:
                pos = li.index(i,p)
                try:
                    while pos != p:
                        if pos - p >1:
                            li[pos],li[pos-1],li[pos-2] = li[pos-1],li[pos-2],li[pos]
                            ansQ.append(pos-2+1)
                            ans += 1
                            pos -= 2
                        else:
                            li[pos-1],li[pos],li[pos+1] = li[pos],li[pos+1],li[pos-1]
                            ans += 2
                            ansQ.append(pos-1+1)
                            ansQ.append(pos-1+1)
                            pos -= 1
                except:
                    print(*li[-20:])
                    print(*il[-20:])
                    print(sol)
                    #print(traceback.format_exc())
    except:
        print(traceback.format_exc())
    if ans<= n**2:
        print(ans)
        print(*ansQ)
    else:
        print(-1)