You are given an array $a$ consisting of $n$ integers.

In one move, you can choose some index $i$ ($1 \le i \le n - 2$) and shift the segment $[a_i, a_{i + 1}, a_{i + 2}]$ cyclically to the right (i.e. replace the segment $[a_i, a_{i + 1}, a_{i + 2}]$ with $[a_{i + 2}, a_i, a_{i + 1}]$). 

Your task is to sort the initial array by no more than $n^2$ such operations or say that it is impossible to do that.

You have to answer $t$ independent test cases.


-----Input-----

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

The first line of the test case contains one integer $n$ ($3 \le n \le 500$) — the length of $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 500$), where $a_i$ is the $i$-th element $a$.

It is guaranteed that the sum of $n$ does not exceed $500$.


-----Output-----

For each test case, print the answer: -1 on the only line if it is impossible to sort the given array using operations described in the problem statement, or the number of operations $ans$ on the first line and $ans$ integers $idx_1, idx_2, \dots, idx_{ans}$ ($1 \le idx_i \le n - 2$), where $idx_i$ is the index of left border of the segment for the $i$-th operation. You should print indices in order of performing operations.


-----Example-----
Input
5
5
1 2 3 4 5
5
5 4 3 2 1
8
8 4 5 2 3 6 7 3
7
5 2 1 6 4 7 3
6
1 2 3 3 6 4

Output
0

6
3 1 3 2 2 3 
13
2 1 1 6 4 2 4 3 3 4 4 6 6 
-1
4
3 3 4 4

Difficulty: introductory

Starter code:

Solutions:
t = int(input())
for _ in range(t):
    n = int(input())
    l = list([int(x)- 1 for x in input().split()])
    out = []

    ll = [(l[i], i) for i in range(n)]
    ll.sort()

    swap = (-1,-1)
    for i in range(n - 1):
        if ll[i][0] == ll[i + 1][0]:
            swap = (ll[i][1],ll[i+1][1])

    newl = [0]*n
    for i in range(n):
        newl[ll[i][1]] = i

    l = newl

    swapN = 0
    for i in range(n):
        for j in range(i + 1, n):
            if l[i] > l[j]:
                swapN += 1

    #print(l)
    if swapN & 1:
        l[swap[0]],l[swap[1]] = l[swap[1]],l[swap[0]]
    #print(l)

    def shift(i):
        out.append(i + 1)
        l[i],l[i+1],l[i+2] = l[i+2],l[i],l[i+1]

    works = True
    done = False

    while not done:
    
        for i in range(n):
            if l[i] != i:
                break
        else:
            done = True

        if done:
            break

        for find in range(i + 1, n):
            if l[find] == i:
                break

        while find - i >= 2:
            find -= 2
            shift(find)

        if find - i == 1:
            if find <= n - 2:
                shift(find - 1)
                shift(find - 1)
            else:
                works = False
                break

    #print(l)
    if works:
        print(len(out))
        print(' '.join(map(str,out)))
    else:
        print(-1)
    #print('---')
        
    


def cnt_inv(a):
    ans = 0
    for i in range(len(a)):
        for f in range(i + 1, len(a)):
            if a[f] < a[i]:
                ans += 1
    return ans

for testcase in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    inv = cnt_inv(a)

    sorted_a = list(sorted(a))

    last_eq = -1
    for i in range(n - 1):
        if sorted_a[i] == sorted_a[i + 1]:
            last_eq = i + 1

    # print("last_eq", last_eq) 
    ans = []
    def shift(pos):
        nonlocal inv
        inv -= int(a[pos] > a[pos + 1]) + int(a[pos] > a[pos + 2]) + int(a[pos + 1] > a[pos + 2])
        a[pos], a[pos + 1], a[pos + 2] = a[pos + 2], a[pos], a[pos + 1]
        inv += int(a[pos] > a[pos + 1]) + int(a[pos] > a[pos + 2]) + int(a[pos + 1] > a[pos + 2])
        ans.append(pos + 1)

    for i in range(n - 3):
        pos = min(list(range(i, n)), key=lambda x: a[x])
        # print(a, val, pos) 
        while pos > i + 1:
            shift(pos - 2)
            pos -= 2
        if pos == i + 1:
            shift(i)
            shift(i)
        if i == last_eq and inv % 2 == 1:
            shift(i)
            shift(i - 1)

    last_min = min(*a[-3:])
    while a[-3] != last_min:
        shift(n - 3)
    
    if n - 3 == last_eq and inv % 2 == 1:
        shift(n - 3)
        shift(n - 4)
        
    cnt = 0
    while not (a[-3] <= a[-2] <= a[-1]):
        shift(n - 3) 
        cnt += 1
        if cnt > 5:
            break
    if cnt > 5:
        print(-1)
    else:
        print(len(ans))
        print(' '.join(map(str, ans)))





def swap(i):

    tmp = a[i+2]
    a[i+2] = a[i+1]
    a[i+1] = a[i]
    a[i] = tmp
    ans.append(i+1)
    #print (*a)

tt = int(input())

for loop in range(tt):

    n = int(input())
    a = list(map(int,input().split()))
    sa = 0.0001

    
    lis = [sa] * 501
    
    b1 = []
    b2 = []
    
    f2 = True
    for i in range(n):
        if lis[a[i]] != sa and f2:
            b1.append(a[i] + lis[a[i]])
            b2.append(a[i])
            f2 = False
        else:
            b1.append(a[i] + lis[a[i]])
            b2.append(a[i] + lis[a[i]])

        lis[a[i]] += sa

    #print (b1)
    #print (b2)   

    ans = []
    a = b1
    for last in range(n-3):

        mi = last
        for i in range(last,n):
            if a[i] < a[mi]:
                mi = i

        while mi != last:

            if mi - last >= 2:
                swap(mi-2)
                mi -= 2
            else:
                swap(mi)
                mi += 1

    while not ( a[-3] < a[-2] and a[-2] < a[-1] ):
        swap(n-3)

        if len(ans) > n**2:
            break

    if len(ans) <= n**2:
        
        print(len(ans))
        print(*ans)
        continue

    ans = []
    a = b2
    for last in range(n-3):

        mi = last
        for i in range(last,n):
            if a[i] < a[mi]:
                mi = i

        while mi != last:

            if mi - last >= 2:
                swap(mi-2)
                mi -= 2
            else:
                swap(mi)
                mi += 1

    while not ( a[-3] < a[-2] and a[-2] < a[-1] ):
        swap(n-3)

        if len(ans) > n**2:
            break

    if len(ans) <= n**2:
        
        print(len(ans))
        print(*ans)
        continue

    print(-1)

    
        
        
    


t = int(input())
for _ in range(t):
    n = int(input())
    l = list([int(x)- 1 for x in input().split()])
    out = []

    ll = [(l[i], i) for i in range(n)]
    ll.sort()

    swap = (-1,-1)
    for i in range(n - 1):
        if ll[i][0] == ll[i + 1][0]:
            swap = (ll[i][1],ll[i+1][1])

    newl = [0]*n
    for i in range(n):
        newl[ll[i][1]] = i

    l = newl

    swapN = 0
    for i in range(n):
        for j in range(i + 1, n):
            if l[i] > l[j]:
                swapN += 1

    #print(l)
    if swapN & 1:
        l[swap[0]],l[swap[1]] = l[swap[1]],l[swap[0]]
    #print(l)

    def shift(i):
        out.append(i + 1)
        l[i],l[i+1],l[i+2] = l[i+2],l[i],l[i+1]

    works = True
    done = False

    while not done:
    
        for i in range(n):
            if l[i] != i:
                break
        else:
            done = True

        if done:
            break

        for find in range(i + 1, n):
            if l[find] == i:
                break

        while find - i >= 2:
            find -= 2
            shift(find)

        if find - i == 1:
            if find <= n - 2:
                shift(find - 1)
                shift(find - 1)
            else:
                works = False
                break

    #print(l)
    if works:
        print(len(out))
        print(' '.join(map(str,out)))
    else:
        print(-1)
    #print('---')
        


t = int(input())
for _ in range(t):
    n = int(input())
    l = list([int(x)- 1 for x in input().split()])
    out = []

    ll = [(l[i], i) for i in range(n)]
    ll.sort()

    swap = (-1,-1)
    for i in range(n - 1):
        if ll[i][0] == ll[i + 1][0]:swap = (ll[i][1],ll[i+1][1])

    newl = [0]*n
    for i in range(n):newl[ll[i][1]] = i

    l = newl

    swapN = 0
    for i in range(n):
        for j in range(i + 1, n):
            if l[i] > l[j]:swapN += 1

    if swapN & 1:l[swap[0]],l[swap[1]] = l[swap[1]],l[swap[0]]

    def shift(i):out.append(i + 1);l[i],l[i+1],l[i+2] = l[i+2],l[i],l[i+1]

    works,done = True,False
   
    while not done:
    
        for i in range(n):
            if l[i] != i:break
        else:done = True

        if done:break

        for find in range(i + 1, n):
            if l[find] == i:break

        while find - i >= 2:
            find -= 2
            shift(find)

        if find - i == 1:
            if find <= n - 2:shift(find - 1);shift(find - 1)
            else:works = False;break

    if works:
        print(len(out))
        print(' '.join(map(str,out)))
    else:
        print(-1)


def change(i,j,k):
	nonlocal a
	a[i],a[j],a[k] = a[k],a[i],a[j]

for nt in range(int(input())):
	n = int(input())
	a = list(map(int,input().split()))
	arr = a[::]
	b = sorted(a)
	if a==b:
		print (0)
		print ()
		continue
	i = 0
	ans = []
	flag = 0
	while i<n:
		if a[i]==b[i]:
			i += 1
			continue
		ind = a[i:].index(b[i])+i
		# print (ind)
		while a[i]!=b[i]:
			if ind==i+1:
				if ind+1>=len(a):
					flag = 1
					break
				ans.append((i,ind,ind+1))
				change(i,ind,ind+1)
				ans.append((i,ind,ind+1))
				change(i,ind,ind+1)
				break
			else:
				ans.append((ind-2,ind-1,ind))
				change(ind-2,ind-1,ind)
				ind -= 2
		if flag:
			break
		i += 1
		# print (a)
	if flag:
		if len(set(a))==n:
			print (-1)
			continue
		else:
			if a[-3]==a[-1]:
				ans.append((n-3,n-2,n-1))
			else:
				ans = []
				a = arr[::]
				flag2 = 0
				temp = sorted(a,reverse=True)
				for i in range(1,n):
					if temp[i]==temp[i-1]:
						number = temp[i]
						break
				i = 0
				while i<n:
					if a[i]==b[i] and (i==0 or a[i]!=a[i-1] or flag2):
						i += 1
						continue
					elif i!=0 and a[i]==a[i-1]:
						if not flag2 and a[i]==number:
							ans.append((i-1,i,i+1))
							change(i-1,i,i+1)
							ans.append((i-1,i,i+1))
							change(i-1,i,i+1)
							ans.append((i,i+1,i+1))
							change(i,i+1,i+2)
							ans.append((i,i+1,i+2))
							change(i,i+1,i+2)
							flag2 = 1
						i += 1
						continue
					# print (i,a,b)
					ind = a[i:].index(b[i])+i
					# print (ind)
					while a[i]!=b[i]:
						if ind==i+1:
							ans.append((i,ind,ind+1))
							change(i,ind,ind+1)
							ans.append((i,ind,ind+1))
							change(i,ind,ind+1)
							break
						else:
							ans.append((ind-2,ind-1,ind))
							change(ind-2,ind-1,ind)
							ind -= 2
					# print (a,i)
					if i!=0 and a[i]==a[i-1] and flag2==0 and a[i]==number:
						ans.append((i-1,i,i+1))
						change(i-1,i,i+1)
						ans.append((i-1,i,i+1))
						change(i-1,i,i+1)
						ans.append((i,i+1,i+1))
						change(i,i+1,i+2)
						ans.append((i,i+1,i+2))
						change(i,i+1,i+2)
						flag2 = 1
					i += 1
					# print (a)
	
	print (len(ans))
	for i in ans:
		print (i[0]+1,end=" ")
	print ()

t = int(input())
for _ in range(t):
    n = int(input())
    l = list(map(lambda x: int(x)- 1, input().split()))
    out = []

    ll = sorted([(l[i], i) for i in range(n)])

    swap = (-1,-1)
    for i in range(n - 1):
        if ll[i][0] == ll[i + 1][0]:swap = (ll[i][1],ll[i+1][1])

    newl = [0]*n
    for i in range(n):newl[ll[i][1]] = i

    l = newl

    swapN = 0
    for i in range(n):
        for j in range(i + 1, n):
            if l[i] > l[j]:swapN += 1

    if swapN & 1:l[swap[0]],l[swap[1]] = l[swap[1]],l[swap[0]]

    def shift(i):out.append(i + 1);l[i],l[i+1],l[i+2] = l[i+2],l[i],l[i+1]

    works,done = True,False
   
    while not done:
        for i in range(n):
            if l[i] != i:break
        else:done = True
        if done:break
        for find in range(i + 1, n):
            if l[find] == i:break
        while find - i >= 2:find -= 2;shift(find)
        if find - i == 1:
            if find <= n - 2:shift(find - 1);shift(find - 1)
            else:works = False;break
    if works:print(len(out));print(' '.join(map(str,out)))
    else:print(-1)         

for _ in range(int(input())):
    n,l,out = int(input()),list(map(lambda x: int(x)- 1, input().split())),[];ll = sorted([(l[i], i) for i in range(n)]);swap = (-1,-1);newl = [0]*n    
    for i in range(n - 1):
        if ll[i][0] == ll[i + 1][0]:swap = (ll[i][1],ll[i+1][1])  
    for i in range(n):newl[ll[i][1]] = i
    l,swapN = newl,0;works,done = True,False
    for i in range(n):
        for j in range(i + 1, n):
            if l[i] > l[j]:swapN += 1
    if swapN & 1:l[swap[0]],l[swap[1]] = l[swap[1]],l[swap[0]]
    def shift(i):out.append(i + 1);l[i],l[i+1],l[i+2] = l[i+2],l[i],l[i+1]       
    while not done:
        for i in range(n):
            if l[i] != i:break
        else:done = True
        if done:break
        for find in range(i + 1, n):
            if l[find] == i:break
        while find - i >= 2:find -= 2;shift(find)
        if find - i == 1:
            if find <= n - 2:shift(find - 1);shift(find - 1)
            else:works = False;break
    if works:print(len(out));print(' '.join(map(str,out)))
    else:print(-1)         

import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')


def rotate(a, i):
    t = a[i+2]
    a[i + 2] = a[i + 1]
    a[i + 1] = a[i]
    a[i] = t


def solve(n, a):
    sa = sorted(a)
    s = []

    rolled = False
    i = 0
    while i < n:
        for j in range(i, n):
            if a[j] == sa[i]:
                break
        while j - i >= 2:
            j -= 2
            rotate(a, j)
            s.append(j+1)
        if i+1 == j:
            if i+2 < n:
                rotate(a, i)
                rotate(a, i)
                s.append(i+1)
                s.append(i+1)
            else:
                if rolled:
                    wi(-1)
                    return

                found = False
                for k in range(n-2, 0, -1):
                    if len(set(a[k-1:k+2])) == 2:
                        found = True
                        break
                if found:
                    if a[k-1] == a[k]:
                        rotate(a, k - 1)
                        rotate(a, k - 1)
                        s.append(k)
                        s.append(k)
                    else:
                        rotate(a, k - 1)
                        s.append(k)
                    rolled = True
                    i = k-2
                else:
                    wi(-1)
                    return

        i += 1

    if len(s) <= n*n:
        wi(len(s))
        wia(s)
    else:
        wi(-1)


def main():
    for _ in range(ri()):
        n = ri()
        a = ria()
        solve(n, a)


def __starting_point():
    main()

__starting_point()

import heapq
import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n=int(input())
    arr=list(map(int,input().split()))
    turned=0
    q=[]
    for i in range(n):
        heapq.heappush(q,arr[i])
        for j in range(i+1,n):
            if arr[i]>arr[j]:
                turned+=1
    if turned==0:
        print(0)
        print('')
    else:
        if n==3:
            if n==len(set(arr)):
                if turned%2==1:
                    print(-1)
                else:
                    cnt=1
                    ans=[1]
                    arr[0],arr[1],arr[2]=arr[2],arr[0],arr[1]
                    if arr[0]<=arr[1]<=arr[2]:
                        print(cnt)
                        print(*ans)
                    else:
                        cnt+=1
                        ans.append(1)
                        print(cnt)
                        print(*ans)
            else:
                cnt=1
                ans=[1]
                arr[0],arr[1],arr[2]=arr[2],arr[0],arr[1]
                if arr[0]<=arr[1]<=arr[2]:
                    print(cnt)
                    print(*ans)
                else:
                    cnt+=1
                    ans.append(1)
                    print(cnt)
                    print(*ans)
            continue
        if n==len(set(arr)):
            if turned%2==1:
                print(-1)
            else:
                cnt=0
                pos=0
                ans=[]
                while pos<n:
                    tmp=heapq.heappop(q)
                    if arr[pos]==tmp:
                        pos+=1
                        continue
                    else:
                        tpos=pos+arr[pos:].index(tmp)
                        while tpos-pos>=2:
                            cnt+=1
                            tpos-=2
                            ans.append(tpos+1)
                            tmp=0
                            if arr[tpos]>arr[tpos+1]:
                                tmp+=1
                            if arr[tpos]>arr[tpos+2]:
                                tmp+=1
                            if arr[tpos+1]>arr[tpos+2]:
                                tmp+=1
                            arr[tpos],arr[tpos+1],arr[tpos+2]=arr[tpos+2],arr[tpos],arr[tpos+1]
                            if arr[tpos]>arr[tpos+1]:
                                tmp-=1
                            if arr[tpos]>arr[tpos+2]:
                                tmp-=1
                            if arr[tpos+1]>arr[tpos+2]:
                                tmp-=1
                            turned-=tmp
                        if tpos-pos==1:
                            cnt+=2
                            tpos-=1
                            ans.append(tpos+1)
                            ans.append(tpos+1)
                            tmp=0
                            if arr[tpos]>arr[tpos+1]:
                                tmp+=1
                            if arr[tpos]>arr[tpos+2]:
                                tmp+=1
                            if arr[tpos+1]>arr[tpos+2]:
                                tmp+=1
                            arr[tpos],arr[tpos+1],arr[tpos+2]=arr[tpos+1],arr[tpos+2],arr[tpos]
                            if arr[tpos]>arr[tpos+1]:
                                tmp-=1
                            if arr[tpos]>arr[tpos+2]:
                                tmp-=1
                            if arr[tpos+1]>arr[tpos+2]:
                                tmp-=1
                            turned-=tmp
                        pos+=1
                print(cnt)
                print(*ans)
        else:
            cnt=0
            pos=0
            ans=[]
            while pos<n-2:
                tmp=heapq.heappop(q)
                if arr[pos]==tmp:
                    pos+=1
                    continue
                else:
                    tpos=pos+arr[pos:].index(tmp)
                    while tpos-pos>=2:
                        cnt+=1
                        tpos-=2
                        ans.append(tpos+1)
                        tmp=0
                        if arr[tpos]>arr[tpos+1]:
                            tmp+=1
                        if arr[tpos]>arr[tpos+2]:
                            tmp+=1
                        if arr[tpos+1]>arr[tpos+2]:
                            tmp+=1
                        arr[tpos],arr[tpos+1],arr[tpos+2]=arr[tpos+2],arr[tpos],arr[tpos+1]
                        if arr[tpos]>arr[tpos+1]:
                            tmp-=1
                        if arr[tpos]>arr[tpos+2]:
                            tmp-=1
                        if arr[tpos+1]>arr[tpos+2]:
                            tmp-=1
                        turned-=tmp
                    if tpos-pos==1:
                        cnt+=2
                        tpos-=1
                        ans.append(tpos+1)
                        ans.append(tpos+1)
                        tmp=0
                        if arr[tpos]>arr[tpos+1]:
                            tmp+=1
                        if arr[tpos]>arr[tpos+2]:
                            tmp+=1
                        if arr[tpos+1]>arr[tpos+2]:
                            tmp+=1
                        arr[tpos],arr[tpos+1],arr[tpos+2]=arr[tpos+1],arr[tpos+2],arr[tpos]
                        if arr[tpos]>arr[tpos+1]:
                            tmp-=1
                        if arr[tpos]>arr[tpos+2]:
                            tmp-=1
                        if arr[tpos+1]>arr[tpos+2]:
                            tmp-=1
                        turned-=tmp
                    pos+=1
            if turned==0:
                print(cnt)
                print(*ans)
            else:
                ttpos=-1
                for i in range(n-2,-1,-1):
                    if arr[i]==arr[i+1]:
                        ttpos=i
                        break
                if ttpos==-1:
                    cnt+=1
                    ans.append(n-2)
                    arr[n-3],arr[n-2],arr[n-1]=arr[n-1],arr[n-3],arr[n-2]
                    if arr[n-3]<=arr[n-2]<=arr[n-1]:
                        print(cnt)
                        print(*ans)
                    else:
                        cnt+=1
                        ans.append(n-3)
                        print(cnt)
                        print(*ans)
                else:
                    cnt+=2
                    ans.append(ttpos+1)
                    ans.append(ttpos+1)
                    arr[ttpos],arr[ttpos+1],arr[ttpos+2]=arr[ttpos+1],arr[ttpos+2],arr[ttpos]
                    turned+=1
                    q=[]
                    for i in range(n):
                        heapq.heappush(q,arr[i])
                    pos=0
                    while pos<n-2:
                        tmp=heapq.heappop(q)
                        if arr[pos]==tmp:
                            pos+=1
                            continue
                        else:
                            tpos=pos+arr[pos:].index(tmp)
                            while tpos-pos>=2:
                                cnt+=1
                                tpos-=2
                                ans.append(tpos+1)
                                arr[tpos],arr[tpos+1],arr[tpos+2]=arr[tpos+2],arr[tpos],arr[tpos+1]
                            if tpos-pos==1:
                                cnt+=2
                                tpos-=1
                                ans.append(tpos+1)
                                ans.append(tpos+1)
                                arr[tpos],arr[tpos+1],arr[tpos+2]=arr[tpos+1],arr[tpos+2],arr[tpos]
                            pos+=1
                    print(cnt)
                    print(*ans)

for _ in range(int(input())):
    n,l,out = int(input()),list(map(lambda x: int(x)- 1, input().split())),[];ll = sorted([(l[i], i) for i in range(n)]);swap = (-1,-1);newl = [0]*n    
    for i in range(n - 1):
        if ll[i][0] == ll[i + 1][0]:swap = (ll[i][1],ll[i+1][1])  
    for i in range(n):newl[ll[i][1]] = i
    l,swapN = newl,0;works,done = True,False
    for i in range(n):
        for j in range(i + 1, n):
            if l[i] > l[j]:swapN += 1
    if swapN & 1:l[swap[0]],l[swap[1]] = l[swap[1]],l[swap[0]]
    def shift(i):out.append(i + 1);l[i],l[i+1],l[i+2] = l[i+2],l[i],l[i+1]       
    while not done:
        for i in range(n):
            if l[i] != i:break
        else:done = True
        if done:break
        for find in range(i + 1, n):
            if l[find] == i:break
        while find - i >= 2:find -= 2;shift(find)
        if find - i == 1:
            if find <= n - 2:shift(find - 1);shift(find - 1)
            else:works = False;break
    if works:print(len(out));print(' '.join(map(str,out)))
    else:print(-1)   

#!/usr/bin/env python3

import heapq
import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n=int(input())
    arr=list(map(int,input().split()))
    q=[]
    for i in range(n):
        heapq.heappush(q,arr[i])
    pos=0
    cnt=0
    ans=[]
    while pos<n-2:
        tmp=heapq.heappop(q)
        if arr[pos]==tmp:
            pos+=1
            continue
        else:
            tpos=pos+arr[pos:].index(tmp)
            while tpos-pos>=2:
                cnt+=1
                tpos-=2
                ans.append(tpos+1)
                arr[tpos],arr[tpos+1],arr[tpos+2]=arr[tpos+2],arr[tpos],arr[tpos+1]
            if tpos-pos==1:
                cnt+=2
                tpos-=1
                ans.append(tpos+1)
                ans.append(tpos+1)
                arr[tpos],arr[tpos+1],arr[tpos+2]=arr[tpos+1],arr[tpos+2],arr[tpos]
            pos+=1
    if arr[n-2]<=arr[n-1]:
        print(cnt)
        print(*ans)
    else:
        ttpos=-1
        for i in range(n-2,-1,-1):
            if arr[i]==arr[i+1]:
                ttpos=i
                break
        if ttpos==-1:
            cnt+=1
            ans.append(n-2)
            arr[n-3],arr[n-2],arr[n-1]=arr[n-1],arr[n-3],arr[n-2]
            if arr[n-3]<=arr[n-2]<=arr[n-1]:
                print(cnt)
                print(*ans)
            else:
                cnt+=1
                ans.append(n-2)
                arr[n-3],arr[n-2],arr[n-1]=arr[n-1],arr[n-3],arr[n-2]
                if arr[n-3]<=arr[n-2]<=arr[n-1]:
                    print(cnt)
                    print(*ans)
                else:
                    print(-1)
        else:
            cnt+=2
            ans.append(ttpos+1)
            ans.append(ttpos+1)
            arr[ttpos],arr[ttpos+1],arr[ttpos+2]=arr[ttpos+1],arr[ttpos+2],arr[ttpos]
            q=[]
            for i in range(n):
                heapq.heappush(q,arr[i])
            pos=0
            while pos<n-2:
                tmp=heapq.heappop(q)
                if arr[pos]==tmp:
                    pos+=1
                    continue
                else:
                    tpos=pos+arr[pos:].index(tmp)
                    while tpos-pos>=2:
                        cnt+=1
                        tpos-=2
                        ans.append(tpos+1)
                        arr[tpos],arr[tpos+1],arr[tpos+2]=arr[tpos+2],arr[tpos],arr[tpos+1]
                    if tpos-pos==1:
                        cnt+=2
                        tpos-=1
                        ans.append(tpos+1)
                        ans.append(tpos+1)
                        arr[tpos],arr[tpos+1],arr[tpos+2]=arr[tpos+1],arr[tpos+2],arr[tpos]
                    pos+=1
            print(cnt)
            print(*ans)

#!/usr/bin/env python3

import heapq
import sys
input=sys.stdin.readline

def shift(k,arr):
    arr[k],arr[k+1],arr[k+2]=arr[k+2],arr[k],arr[k+1]

def solve(pos,cnt,ans,arr):
    n=len(arr)
    q=[]
    for i in range(n):
        heapq.heappush(q,arr[i])
    while pos<n-2:
        tmp=heapq.heappop(q)
        if arr[pos]==tmp:
            pos+=1
            continue
        else:
            tpos=pos+arr[pos:].index(tmp)
            while tpos-pos>=2:
                cnt+=1
                tpos-=2
                ans.append(tpos+1)
                shift(tpos,arr)
            if tpos-pos==1:
                cnt+=2
                tpos-=1
                ans.append(tpos+1)
                ans.append(tpos+1)
                shift(tpos,arr)                
                shift(tpos,arr)
            pos+=1
    return cnt,ans

t=int(input())
for _ in range(t):
    n=int(input())
    arr=list(map(int,input().split()))
    cnt,ans=solve(0,0,[],arr)
    if arr[n-2]<=arr[n-1]:
        print(cnt)
        print(*ans)
    else:
        ttpos=-1
        for i in range(n-2,-1,-1):
            if arr[i]==arr[i+1]:
                ttpos=i
                break
        if ttpos!=-1:
            cnt+=2
            ans.append(ttpos+1)
            ans.append(ttpos+1)            
            shift(ttpos,arr)
            shift(ttpos,arr)
            cnt,ans=solve(0,cnt,ans,arr)
            print(cnt)
            print(*ans)
        else:
            cnt+=1
            ans.append(n-2)
            shift(n-3,arr)
            if arr[n-3]<=arr[n-2]<=arr[n-1]:
                print(cnt)
                print(*ans)
            else:
                cnt+=1
                ans.append(n-2)
                shift(n-3,arr)
                if arr[n-3]<=arr[n-2]<=arr[n-1]:
                    print(cnt)
                    print(*ans)
                else:
                    print(-1)

for _ in range(int(input())):
    n,l,out = int(input()),list(map(lambda x: int(x)- 1, input().split())),[];ll = sorted([(l[i], i) for i in range(n)]);swap = (-1,-1);newl = [0]*n    
    for i in range(n - 1):
        if ll[i][0] == ll[i + 1][0]:swap = (ll[i][1],ll[i+1][1])  
    for i in range(n):newl[ll[i][1]] = i
    l,swapN = newl,0;works,done = True,False
    for i in range(n):
        for j in range(i + 1, n):
            if l[i] > l[j]:swapN += 1
    if swapN & 1:l[swap[0]],l[swap[1]] = l[swap[1]],l[swap[0]]
    def shift(i):out.append(i + 1);l[i],l[i+1],l[i+2] = l[i+2],l[i],l[i+1]       
    while not done:
        for i in range(n):
            if l[i] != i:break
        else:done = True
        if done:break
        for find in range(i + 1, n):
            if l[find] == i:break
        while find - i >= 2:find -= 2;shift(find)
        if find - i == 1:
            if find <= n - 2:shift(find - 1);shift(find - 1)
            else:works = False;break
    if works:print(len(out));print(' '.join(map(str,out)))
    else:print(-1)         

res, a = [], []


def rot(i: int) -> None:
    nonlocal res, a
    res.append(i + 1)
    a[i], a[i+1], a[i+2] = a[i+2], a[i], a[i+1]
    #print(f'Rotation on {i}: {a}')


def solve():
    nonlocal res, a
    res.clear()
    input()
    a = [int(i) for i in input().split()]
    s = sorted(a)
    for i in range(len(a) - 2):
        if a[i] == s[i]:
            continue
        j = a.index(s[i], i, len(a))
        while j != i:
            if j - i >= 2:
                j -= 2
                rot(j)
            else:
                rot(i)
                j += 1
    if any(a[i] > a[i + 1] for i in range(len(a) - 1)):

        for i in range(len(a) - 3, -1, -1):
            while a[i + 2] < a[i] or a[i + 2] < a[i + 1]:
                rot(i)

        if all(a[i] != a[i + 1] for i in range(len(a) - 2)):
            print(-1)
            return

    print(len(res))
    print(' '.join(str(i) for i in res))


t = int(input())
while t > 0:
    t -= 1
    solve()


for _ in range(int(input())):
    n,l,out = int(input()),list(map(lambda x: int(x)- 1, input().split())),[];ll = sorted([(l[i], i) for i in range(n)]);swap = (-1,-1);newl = [0]*n    
    for i in range(n - 1):
        if ll[i][0] == ll[i + 1][0]:swap = (ll[i][1],ll[i+1][1])  
    for i in range(n):newl[ll[i][1]] = i
    l,swapN = newl,0;works,done = True,False
    for i in range(n):
        for j in range(i + 1, n):
            if l[i] > l[j]:swapN += 1
    if swapN & 1:l[swap[0]],l[swap[1]] = l[swap[1]],l[swap[0]]
    def shift(i):out.append(i + 1);l[i],l[i+1],l[i+2] = l[i+2],l[i],l[i+1]       
    while not done:
        for i in range(n):
            if l[i] != i:break
        else:done = True
        if done:break
        for find in range(i + 1, n):
            if l[find] == i:break
        while find - i >= 2:find -= 2;shift(find)
        if find - i == 1:
            if find <= n - 2:shift(find - 1);shift(find - 1)
            else:works = False;break
    if works:print(len(out));print(' '.join(map(str,out)))
    else:print(-1)

import collections

line = input()
t = int(line)
for _i in range(t):
    
    line = input()
    n = int(line)
    line = input()
    nums = [int(i) for i in line.split(' ')]
    
    res = collections.deque()
    for i in range(n - 2):
        for j in range(n - 3, i-1, -1):
            if nums[j + 2] < nums[j + 1] and nums[j + 2] < nums[j]:
                a, b, c = nums[j + 2], nums[j + 1], nums[j]
                nums[j], nums[j + 1], nums[j + 2] = a, c, b
                res.append(j + 1)
        if nums[i] > nums[i + 1]:
            a, b, c = nums[i], nums[i + 1], nums[i + 2]
            nums[i], nums[i + 1], nums[i + 2] = b, c, a
            res.append(i + 1)
            res.append(i + 1)
        
        # print(nums)
    if nums[n - 3] == nums[n - 1] and nums[n - 2] > nums[n - 1]:
        res.append(n - 2)
        nums[n - 1], nums[n - 2] = nums[n - 2], nums[n - 1]
    if nums[-1] < nums[-2]:
        i = n - 2
        while i >= 0 and nums[i] != nums[i + 1]:
            i -= 1
        if i < 0:
            print(-1)
        else:
            while i < n - 2:
                res.append(i + 1)
                res.append(i + 1)
                i += 1
            print(len(res))
            for i in res:
                print(i, end= ' ')
            print()
    else:
        print(len(res))
        for i in res:
            print(i, end= ' ')
        print()



def swap(i,j):
    arr[i],arr[j]=arr[j],arr[i]
def inversion(li):
    n=len(li)
    inversions=0
    for i in range(n):
        for j in range(i+1,n):
            if(li[j]<li[i]):
                inversions+=1
    return inversions
def right_shift(i):
    arr[i],arr[i+1],arr[i+2]=[arr[i+2],arr[i],arr[i+1]]
t=int(input())
for you in range(t):
    n=int(input())
    l=input().split()
    arr=[int(i) for i in l]
    arr1=list(arr)
    lfi=[]
    lo=[]
    for i in range(n):
        lo.append((arr[i],i))
    lo.sort()
    hashi=dict()
    for i in range(n):
        hashi[lo[i][1]]=i+1
    arr=[]
    for i in range(n):
        arr.append(hashi[i])
    poss=1
    if(inversion(arr)%2):
        for i in range(n):
            for j in range(i+1,n):
                if(arr1[i]==arr1[j]):
                    swap(i,j)
                    poss=0
                    break
            if(poss==0):
                break
    z=list(arr)
    z.sort()
    for j in range(n):
        for i in range(n-2-j):
            maxa=max(arr[i],arr[i+1],arr[i+2])
            if(maxa==arr[i+2]):
                continue
            elif(maxa==arr[i+1]):
                lfi.append(i)
                right_shift(i)
            else:
                lfi.append(i)
                lfi.append(i)
                right_shift(i)
                right_shift(i)
    if(arr==z):
        print(len(lfi))
        for i in lfi:
            print(i+1,end=" ")
        print()
    else:
        print(-1)

import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

for _ in range(II()):
    def rot(top):
        aa[top],aa[top+1],aa[top+2]=aa[top+2],aa[top],aa[top+1]

    n=II()
    aa=LI()
    bb=aa[:]
    bb.sort()
    ans=[]
    for i in range(n-2):
        j=i
        while aa[j]!=bb[i]:j+=1
        while j>i:
            if i==j-1:
                rot(i)
                rot(i)
                ans+=[i+1,i+1]
                j=i
            else:
                rot(j-2)
                ans+=[j-1]
                j-=2
            #print(i,aa,bb,ans)

    if bb[-1]==aa[-1]:
        print(len(ans))
        print(*ans)
    else:
        for i in range(n-3,-1,-1):
            rot(i)
            ans+=[i+1]
            if aa[i]==aa[i+1]:
                print(len(ans))
                print(*ans)
                break
        else:print(-1)


res, a = [], []
 
 
def rot(i: int) -> None:
    nonlocal res, a
    res.append(i + 1)
    a[i], a[i+1], a[i+2] = a[i+2], a[i], a[i+1]
    #print(f'Rotation on {i}: {a}')
 
 
def solve():
    nonlocal res, a
    res.clear()
    input()
    a = [int(i) for i in input().split()]
    s = sorted(a)
    for i in range(len(a) - 2):
        if a[i] == s[i]:
            continue
        j = a.index(s[i], i, len(a))
        while j != i:
            if j - i >= 2:
                j -= 2
                rot(j)
            else:
                rot(i)
                j += 1
    if any(a[i] > a[i + 1] for i in range(len(a) - 1)):
 
        for i in range(len(a) - 3, -1, -1):
            while a[i + 2] < a[i] or a[i + 2] < a[i + 1]:
                rot(i)
 
        if all(a[i] != a[i + 1] for i in range(len(a) - 2)):
            print(-1)
            return
 
    print(len(res))
    print(' '.join(str(i) for i in res))
 
 
t = int(input())
while t > 0:
    t -= 1
    solve()