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

Starter code:

Solutions:
import io
import os
from collections import Counter, deque
DEBUG = False

def solve(N, A):
	original = list(A)
	sortedA = sorted(A)
	if False and N <= 5:

		def doMove(A, i):
			assert i + 2 < N
			A = list(A)
			return tuple(A[:i] + [A[i + 2], A[i], A[i + 1]] + A[i + 3:])
		moves = None
		source = tuple(A)
		dest = tuple(sortedA)
		q = deque([source])
		moveFromParent = {source: None}
		while q:
			node = q.popleft()
			if node == dest:
				moves = []
				while moveFromParent[node] is not None:
					i = moveFromParent[node]
					moves.append(i)
					node = doMove(node, i)
					node = doMove(node, i)
				moves = moves[::-1]
				break
			for i in range(N - 2):
				nbr = doMove(node, i)
				if nbr not in moveFromParent:
					q.append(nbr)
					moveFromParent[nbr] = i
		if moves is None:
			return -1
	else:
		moves = []
		for (i, target) in enumerate(sortedA):
			index = A.index(target)
			del A[index]
			j = i + index
			while j >= i + 2:
				j -= 2
				moves.append(j)
			assert i <= j <= i + 1
			if j == i:
				continue
			assert j == i + 1
			assert len(A) > 0
			if len(A) >= 2:
				moves.append(i)
				moves.append(i)
				(A[0], A[1]) = (A[1], A[0])
				continue
			assert len(A) == 1
			if A[0] == target:
				break
			if sortedA[i - 1] == target:
				moves.append(i - 1)
				break
			assert sortedA[i - 1] < target < A[0]
			assert j == N - 1
			dupes = set((k for (k, v) in Counter(sortedA).items() if v > 1))
			if not dupes:
				return -1
			while sortedA[j - 1] not in dupes:
				moves.append(j - 2)
				j -= 2
			assert sortedA[j - 1] in dupes
			if sortedA[j] in dupes:
				moves.append(j - 1)
				j += 1
			else:
				assert sortedA[j - 2] in dupes
				moves.append(j - 2)
				moves.append(j - 2)
				j -= 1
			while j != N - 2:
				moves.append(j)
				moves.append(j)
				j += 2
			break
	if DEBUG:
		A = original
		for i in moves:
			assert i + 3 <= N
			A[i:i + 3] = (A[i + 2], A[i], A[i + 1])
		assert A == sortedA
	if len(moves) <= N * N:
		return str(len(moves)) + '\n' + ' '.join((str(x + 1) for x in moves))
	return -1
if DEBUG:
	import random
	random.seed(0)
	for t in range(1000):
		A = [random.randint(0, 10) for i in range(100)]
		solve(len(A), A)
	A = [1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 11]
	print(solve(len(A), A))
	A = [1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 11]
	print(solve(len(A), A))
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
for t in range(T):
	(N,) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	ans = solve(N, A)
	print(ans)


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))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	for _ in range(N()):
		n = N()
		arr = RLL()
		sarr = sorted(arr)
		res = []

		def swap(i):
			res.append(i + 1)
			(arr[i], arr[i + 1], arr[i + 2]) = (arr[i + 2], arr[i], arr[i + 1])
		for i in range(n - 2):
			now = arr[i]
			if now == sarr[i]:
				continue
			for j in range(i + 1, n):
				if arr[j] == sarr[i]:
					ind = j
					while ind - 2 >= i:
						swap(ind - 2)
						ind -= 2
					if ind != i:
						swap(i)
						swap(i)
		for i in range(n - 1, 1, -1):
			now = arr[i]
			if now == sarr[i]:
				continue
			for j in range(i - 1, -1, -1):
				if arr[j] == sarr[i]:
					ind = j
					while ind + 2 <= i:
						swap(ind)
						swap(ind)
						ind += 2
					if ind != i:
						swap(ind - 1)
		if sarr != arr:
			print(-1)
		else:
			print(len(res))
			print(*res)
main()


t = int(input())
from copy import deepcopy

def solve():
	d = [-1] * n
	for i in range(n):
		(x, y) = l2[i]
		d[y] = i
	ans = []
	count = 0
	for i in range(n - 1, 1, -1):
		y = d.index(i)
		while y < i:
			count += 1
			if y == i - 1:
				ans.append(y)
				(d[y - 1], d[y], d[y + 1]) = (d[y + 1], d[y - 1], d[y])
			else:
				ans.append(y + 1)
				(d[y], d[y + 1], d[y + 2]) = (d[y + 2], d[y], d[y + 1])
			y += 1
	if d[0] <= d[1] <= d[2]:
		print(count)
		print(*ans)
		return True
	else:
		check = False
		c = 0
		while c < 3:
			ans.append(1)
			(d[0], d[1], d[2]) = (d[2], d[0], d[1])
			count += 1
			c += 1
			if d[0] <= d[1] <= d[2]:
				check = True
				break
		if check:
			print(count)
			print(*ans)
			return True
		else:
			return False
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l2 = sorted([[x, i] for (i, x) in enumerate(l)])
	if solve() == False:
		for i in range(n - 1):
			if l2[i][0] == l2[i + 1][0]:
				(l2[i][1], l2[i + 1][1]) = (l2[i + 1][1], l2[i][1])
				break
		if solve() == False:
			print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(lambda x: int(x) - 1, 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 = 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
	if works:
		print(len(out))
		print(' '.join(map(str, out)))
	else:
		print(-1)


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


def g(A, i, y, move):
	n = min(i, y - 2)
	(A[n - 1], A[n], A[n + 1]) = (A[n + 1], A[n - 1], A[n])
	move.append(max(1, n))

def f(A, x, y, move):
	i = A.index(x) + 1
	while i < y:
		g(A, i, y, move)
		i += 1
for tc in range(int(input())):
	n = int(input())
	A = input().split(' ')
	B = []
	S = []
	Amove = []
	Bmove = []
	for i in range(n):
		A[i] = int(A[i])
		B.append(A[i])
		S.append(A[i])
	S.sort()
	dupin = -1
	for i in range(n - 1):
		if S[i] == S[i + 1]:
			dupin = i
			break
	if dupin == -1:
		for i in range(n - 2):
			f(A, S[n - i - 1], n - i, Amove)
		if A[0] > A[1]:
			print(-1)
		else:
			print(len(Amove))
			for i in Amove:
				print(i, end=' ')
			print()
	else:
		for i in range(n - 2):
			f(A, S[n - i - 1], n - i, Amove)
		if A[0] <= A[1]:
			print(len(Amove))
			for i in Amove:
				print(i, end=' ')
			print()
			continue
		elif A[0] == A[2]:
			Amove.append(1)
			Amove.append(1)
			print(len(Amove))
			for i in Amove:
				print(i, end=' ')
			print()
			continue
		else:
			for i in range(n - 2):
				f(B, S[n - i - 1], n - i, Bmove)
				if n - i - 1 == dupin:
					g(B, n - i - 1, n, Bmove)
					g(B, n - i - 2, n, Bmove)
			print(len(Bmove))
			for i in Bmove:
				print(i, end=' ')
			print()


from sys import stdin, stdout

def cyclic_shifts_sorting(n, a):
	dic = {}
	dupi = -1
	dupj = -1
	for i in range(n):
		a[i] *= 1000
		if a[i] in dic:
			k = a[i]
			a[i] += dic[k][0]
			dic[k][0] += 1
			if dupi == -1:
				dupi = dic[k][1]
				dupj = i
		else:
			dic[a[i]] = [1, i]
	iv = 0
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				iv += 1
	if iv % 2 == 1:
		if dupi == -1:
			return [-1]
		else:
			tmp = a[dupi]
			a[dupi] = a[dupj]
			a[dupj] = tmp
	sa = sorted(a)
	res = []
	for i in range(n):
		if sa[i] == a[i]:
			continue
		idx = -1
		for j in range(n):
			if a[j] == sa[i]:
				idx = j
				break
		while idx >= i + 2:
			tmp = a[idx]
			a[idx] = a[idx - 1]
			a[idx - 1] = a[idx - 2]
			a[idx - 2] = tmp
			res.append(idx - 2 + 1)
			idx -= 2
		if idx > i:
			tmp = a[idx]
			a[idx] = a[idx + 1]
			a[idx + 1] = a[idx - 1]
			a[idx - 1] = tmp
			res.append(idx - 1 + 1)
			res.append(idx - 1 + 1)
			idx -= 1
	return [len(res), res]
t = int(stdin.readline())
for i in range(t):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	res = cyclic_shifts_sorting(n, a)
	stdout.write(str(res[0]) + '\n')
	if res[0] > -1:
		stdout.write(' '.join(map(str, res[1])) + '\n')


t = 1
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a = [(a[i], i) for i in range(n)]
	a.sort()
	rev = 0
	for i in range(n):
		(val, id) = a[i]
		for j in range(i):
			(sval, sid) = a[j]
			if sid > id:
				rev += 1
	if rev % 2 == 1:
		for i in range(1, n):
			if a[i][0] == a[i - 1][0]:
				(a[i - 1], a[i]) = (a[i], a[i - 1])
				break
		else:
			print(-1)
			continue
	A = [-1] * n
	for i in range(n):
		(val, id) = a[i]
		A[id] = i + 1
	a = [0] + A
	ID = [-1] * (n + 1)
	for i in range(1, n + 1):
		ID[a[i]] = i
	goal = 1
	res = []

	def swap(i):
		res.append(i)
		(ID[a[i]], ID[a[i + 1]], ID[a[i + 2]]) = (i + 1, i + 2, i)
		(a[i], a[i + 1], a[i + 2]) = (a[i + 2], a[i], a[i + 1])
	while n >= goal:
		start = ID[goal]
		if (start - goal) % 2 == 1:
			if start == n:
				swap(start - 2)
				swap(start - 2)
				start = ID[goal]
			else:
				swap(start - 1)
				start = ID[goal]
		while start != goal:
			swap(start - 2)
			start = ID[goal]
		goal += 1
	print(len(res))
	print(*res)


import os
import sys
from io import BytesIO, IOBase
from bisect import bisect_left, bisect_right
import threading
from collections import Counter, defaultdict
arr = []

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		a = arr.copy()
		a.sort()
		mis = 0
		cnt = [0] * 501
		for i in arr:
			cnt[i] += 1
		b = True
		for i in cnt:
			if i > 1:
				b = False
		for i in range(n):
			for j in range(i + 1, n):
				if arr[j] < arr[i]:
					mis += 1
		if mis % 2 == 1 and b:
			print(-1)
		else:
			ans = []
			st = n - 1
			while st > 1:
				ma_ = max(arr)
				ind = arr.index(ma_)
				for i in range(ind, st - 1):
					(arr[i], arr[i + 1], arr[i + 2]) = (arr[i + 2], arr[i], arr[i + 1])
					ans.append(i)
				if arr[st] != ma_:
					(arr[st - 2], arr[st - 1], arr[st]) = (arr[st], arr[st - 2], arr[st - 1])
					ans.append(st - 2)
				arr[st] = -1
				st -= 1
			if arr[0] > arr[1]:
				i = 1
				while i + 2 < len(a) and a[i] != a[i - 1]:
					ans.append(i)
					ans.append(i - 1)
					(a[i + 1], a[i + 2]) = (a[i + 2], a[i + 1])
					i += 2
					if i < n - 1 and a[i + 1] == a[i - 1]:
						ans.append(i - 1)
						ans.append(i - 1)
						break
			for i in range(len(ans)):
				ans[i] += 1
			print(len(ans))
			print(*ans)
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))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = []
	for i in range(n):
		for j in range(n - 2):
			if l[j] > l[j + 1]:
				(l[j], l[j + 2]) = (l[j + 2], l[j])
				(l[j], l[j + 1]) = (l[j + 1], l[j])
				s.append(j + 1)
				s.append(j + 1)
			elif l[j + 1] > l[j + 2]:
				(l[j], l[j + 1]) = (l[j + 1], l[j])
				(l[j], l[j + 2]) = (l[j + 2], l[j])
				s.append(j + 1)
	if l != sorted(l):
		print(-1)
	else:
		print(len(s))
		print(*s)


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
		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
	if flag:
		if len(set(a)) == n:
			print(-1)
			continue
		elif 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
				ind = a[i:].index(b[i]) + i
				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
				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(len(ans))
	for i in ans:
		print(i[0] + 1, end=' ')
	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
	ans = []

	def shift(pos):
		global 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(range(i, n), key=lambda x: a[x])
		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)))


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(' ')]
	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)
	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)
	except:
		print(traceback.format_exc())
	if ans <= n ** 2:
		print(ans)
		print(*ansQ)
	else:
		print(-1)


class IndexingList:
	from collections import defaultdict

	def __init__(self, lst):
		self.lst = lst
		self.indexes = self.defaultdict(set)
		for (i, e) in enumerate(self.lst):
			self.indexes[e].add(i)

	def __getitem__(self, k):
		assert isinstance(k, int)
		return self.lst[k]

	def __setitem__(self, k, v):
		assert isinstance(k, int)
		old_v = self.lst[k]
		self.indexes[old_v].remove(k)
		self.indexes[v].add(k)
		self.lst[k] = v

	def __len__(self):
		return len(self.lst)

	def index(self, k):
		s = self.indexes[k]
		if len(s) == 0:
			assert False
		return next(iter(s))

	def __repr__(self):
		return self.lst.__repr__()

	def __eq__(self, other):
		if isinstance(other, IndexingList):
			return self.lst == other.lst
		elif isinstance(other, list):
			return self.lst == other
		assert False
num_calls = 0

def swaps(A):
	global num_calls
	A = IndexingList(A)
	ret = []
	for k in range(len(A) - 1, 1, -1):
		assert A.index(k) <= k
		while A.index(k) < k:
			num_calls += 1
			s = max(A.index(k) - 1, 0)
			ret += [s]
			(A[s], A[s + 1], A[s + 2]) = (A[s + 2], A[s], A[s + 1])
	if sorted(A) != A:
		return None
	return [x + 1 for x in ret]

def ans(A):
	seen = set()
	duplicate = None
	for a in A:
		if a in seen:
			duplicate = a
			break
		else:
			seen.add(a)
	A = [(e, i) for (i, e) in enumerate(A)]
	A = sorted(A)
	A = [(i, j, e) for (j, (e, i)) in enumerate(A)]
	A = sorted(A)
	A2 = None
	if duplicate is not None:
		duplicate_indices = set()
		for (i, (_, _, e)) in enumerate(A):
			if e == duplicate:
				duplicate_indices.add(i)
		assert len(duplicate_indices) >= 2
		(p, q) = list(duplicate_indices)[0:2]
		A2 = A[:]
		(A2[p], A2[q]) = (A2[q], A2[p])
		A2 = [j for (i, j, e) in A2]
	A = [j for (i, j, e) in A]
	s = swaps(A)
	s2 = None
	if A2 is not None:
		s2 = swaps(A2)
	if s is not None:
		print(len(s))
		print(*s)
	elif s2 is not None:
		print(len(s2))
		print(*s2)
	else:
		print(-1)
T = int(input())
for _ in range(T):
	input()
	A = input().split(' ')
	A = list(map(int, A))
	ans(A)


from random import randint
it = lambda : list(map(int, input().strip().split()))

def solve():
	N = int(input())
	A = it()
	inversion = 0
	duplicate = None
	for i in range(N):
		for j in range(i):
			if A[j] > A[i]:
				inversion += 1
			elif A[j] == A[i]:
				duplicate = A[j]
	if inversion % 2:
		if duplicate is None:
			print(-1)
			return
		l = 2
		for i in range(N - 1, -1, -1):
			if A[i] == duplicate:
				l -= 1
				if l == 0:
					A[i] += 0.1
					break
	A = [[a, i] for (i, a) in enumerate(A)]
	B = sorted(A)
	I = []
	for i in range(N):
		if A[i] == B[i]:
			continue
		for idx in range(i + 1, N):
			if A[idx] == B[i]:
				break
		while idx > i:
			if idx >= i + 2:
				idx -= 2
				I.append(idx + 1)
				(A[idx], A[idx + 1], A[idx + 2]) = (A[idx + 2], A[idx], A[idx + 1])
			else:
				idx -= 1
				I.extend([idx + 1] * 2)
				(A[idx], A[idx + 1], A[idx + 2]) = (A[idx + 1], A[idx + 2], A[idx])
	print(len(I))
	print(' '.join(map(str, I)))
T = int(input())
for _ in range(T):
	solve()


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


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


(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])

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


from sys import *
for t in range(int(stdin.readline())):
	n = int(stdin.readline())
	vec = [int(x) for x in stdin.readline().split()]
	ind = [x for x in range(n)]
	ans = []

	def shift(pos):
		ans.append(pos + 1)
		(vec[pos], vec[pos + 1], vec[pos + 2]) = (vec[pos + 2], vec[pos], vec[pos + 1])
	aux = vec.copy()
	aux.sort()
	for i in range(n):
		if vec[i] != aux[i]:
			j = 0
			for _ in range(i + 1, n):
				if vec[_] == aux[i]:
					j = _
					break
			while j - 2 >= i:
				j -= 2
				shift(j)
			if vec[i] == aux[i]:
				continue
			if i >= n - 2:
				break
			shift(i)
			shift(i)
	if vec[-1] < vec[-2] and vec[-1] == vec[-3]:
		shift(n - 3)
	if vec[-1] < vec[-2]:
		pos = 0
		for i in reversed(range(1, n - 2)):
			if vec[i] == vec[i - 1]:
				pos = i
				break
		if pos == 0:
			stdout.write(str(-1) + '\n')
			continue
		for i in reversed(range(pos - 1, n - 2)):
			shift(i)
	if vec[-1] < vec[-2]:
		stdout.write(str(-1) + '\n')
		continue
	stdout.write(str(len(ans)) + '\n')
	for i in ans:
		stdout.write(str(i) + ' ')
	stdout.write('\n')


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)


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


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
for _ in range(inp()):
	n = inp()
	a = inpl()
	b = a[:]
	b.sort()
	res = []
	for i in range(n - 2):
		now = b[i]
		for j in range(i, n):
			if a[j] == now:
				break
		while j - i > 1:
			res.append(j - 2 + 1)
			(a[j - 2], a[j - 1], a[j]) = (a[j], a[j - 2], a[j - 1])
			j -= 2
		if j - i == 1:
			res.append(i + 1)
			res.append(i + 1)
			(a[i], a[i + 1], a[i + 2]) = (a[i + 1], a[i + 2], a[i])
	if a[n - 2] > a[n - 1]:
		if len(set(a)) == n:
			print(-1)
			continue
		same = -1
		for i in range(n - 1):
			if a[i] == a[i + 1]:
				same = i
		if same == -1:
			for i in range(n - 2):
				if a[i] == a[-1]:
					same = i
		for i in range(same, n - 2)[::-1]:
			res.append(i + 1)
	print(len(res))
	print(*res)


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)


def swaps(A):
	ret = []
	for k in range(len(A) - 1, 1, -1):
		assert A.index(k) <= k
		while A.index(k) < k:
			s = max(A.index(k) - 1, 0)
			ret += [s]
			(A[s], A[s + 1], A[s + 2]) = (A[s + 2], A[s], A[s + 1])
	if sorted(A) != A:
		return None
	return [x + 1 for x in ret]

def ans(A):
	seen = set()
	duplicate = None
	for a in A:
		if a in seen:
			duplicate = a
			break
		else:
			seen.add(a)
	A = [(e, i) for (i, e) in enumerate(A)]
	A = sorted(A)
	A = [(i, j, e) for (j, (e, i)) in enumerate(A)]
	A = sorted(A)
	A2 = None
	if duplicate is not None:
		duplicate_indices = set()
		for (i, (_, _, e)) in enumerate(A):
			if e == duplicate:
				duplicate_indices.add(i)
		assert len(duplicate_indices) >= 2
		(p, q) = list(duplicate_indices)[0:2]
		A2 = A[:]
		(A2[p], A2[q]) = (A2[q], A2[p])
		A2 = [j for (i, j, e) in A2]
	A = [j for (i, j, e) in A]
	s = swaps(A)
	s2 = None
	if A2 is not None:
		s2 = swaps(A2)
	if s is not None:
		print(len(s))
		print(*s)
	elif s2 is not None:
		print(len(s2))
		print(*s2)
	else:
		print(-1)
T = int(input())
for _ in range(T):
	input()
	A = input().split(' ')
	A = list(map(int, A))
	ans(A)