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 $\frac{n}{2}$ the following equation is true: $a_i + a_{n - i + 1} = x$, where $x$ should be the same for all $\frac{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 \le t \le 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 \le n \le 2 \cdot 10^5, 1 \le k \le 2 \cdot 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, \dots, a_n$ ($1 \le a_i \le 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 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$, $\sum k \le 2 \cdot 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

Difficulty: introductory

Starter code:

Solutions:
import sys
def input():
	return sys.stdin.readline()[:-1]

t = int(input())
for _ in range(t):
	n, k = map(int, input().split())
	a = list(map(int, input().split()))
	cum = [0 for _ in range(2*k+2)]
	for i in range(n//2):
		x, y = a[i], a[n-i-1]
		cum[2] += 2
		cum[min(x, y)+1] -= 1
		cum[x+y] -= 1
		cum[x+y+1] += 1
		cum[max(x, y)+k+1] += 1
		cum[2*k+1] -= 2
	ans = n
	for i in range(2, 2*k+1):
		cum[i] += cum[i-1]
		ans = min(ans, cum[i])
	print(ans)

from sys import stdin
input = stdin.readline
t = int(input())
for iwuehufiew in range(t):
	n, k = list(map(int, input().split()))
	l = list(map(int,input().split()))
	odc = [[1 + min(l[i],l[n-1-i]), k+max(l[i],l[n-1-i])] for i in range(n//2)]
	cyk = [0] * (2*k+2)
	for o in odc:
		cyk[o[0]] += 1
		cyk[o[1] + 1] -= 1
	cov = [0] * (2*k+2)
	cov[0] = cyk[0]
	for i in range(1,2*k+2):
		cov[i] = cov[i-1] + cyk[i]
	ilosc = [0] * (2*k+1)
	for i in range(n//2):
		ilosc[l[i]+l[n-1-i]] += 1
	wyn = 759237598237985732489
	for i in range(2*k+1):
		a = cov[i] + (n//2 - cov[i]) * 2 - ilosc[i]
		wyn = min(wyn,a)
	print(wyn)


def __starting_point():
    n = int(input())
    
    for i in range(n):
        h = list(map(int, input().rstrip().split()))
        N = h[0]
        K = h[1]
        h = list(map(int, input().rstrip().split()))
        t = [0]*(2*K+2)
        for i in range(N//2):
            t[h[i]+h[N-i-1]] -= 1
            t[h[i]+h[N-i-1]+1] += 1
            t[max(h[i],h[N-i-1])+K+1] += 1
            t[min(h[i],h[N-i-1])+1] -= 1
        v = N
        minv = N
        for i in range(2*K+2):
            v += t[i]
            if v < minv:
                minv = v
        print(minv)

__starting_point()

class BIT():
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        self._add(r, val)
        self._add(l, -val)

import sys
input = sys.stdin.readline


t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    b = a[n // 2:n][::-1]
    a = a[0:n // 2]
    
    bit = BIT(2 * k + 1)
    bit.add(0, 2 * k + 1, (2 * n // 2))
    for i in range(n // 2):
        ran = [min(a[i] + 1, b[i] + 1), max(a[i] + k + 1, b[i] + k + 1)]
        bit.add(ran[0], ran[1], -1)
        bit.add(a[i] + b[i], a[i] + b[i] + 1, -1)
    print(min([bit.get_val(i) for i in range(2 * k + 1)]))


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
# import io, os
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().split()]
def st():return input()
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input()]
def li3():return [int(i) for i in input()]


for _ in range(val()):
    n,k = li()
    l = li()
    cnt = Counter()
    mins = []
    maxs = []
    sums = []
    arr = [0]*(2*k + 5)
    for i in range(n//2):
        cnt[l[i] + l[n-i-1]] += 1
        a,b = max(l[i],l[n-i-1]),min(l[i],l[n-i-1])


        arr[b] += 1
        arr[a + k] -= 1


        maxs.append(a + k - b)
        mins.append(b + 1)

    mins.sort()
    maxs.sort()

    ans = n
    curr = arr[1]
    for i in range(2,2*k + 1,1):
        onecost = curr - cnt[i]
        twocost =  n//2 - curr
        ans = min(ans,onecost + twocost*2)
        curr += arr[i]
    print(ans)


for f in range(int(input())):
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    nh=n//2
    su=[0]*(2*k+1)
    mi=[0]*nh
    ma=[0]*nh
    for i in range(nh):
        su[a[i]+a[-i-1]]+=1
        mi[i]=min(a[i],a[-i-1])+1
        ma[i]=max(a[i],a[-i-1])+k
    mi.sort()
    ma.sort()
    mii=0
    maa=0
    sol=n
    for i in range(2*k+1):
        while mii<nh and mi[mii]<=i:
            mii+=1
        while maa<nh and ma[maa]<i:
            maa+=1
        sol=min(sol,n-su[i]-mii+maa)
    print(sol)

t = int(input())
for _ in range(t):
    n, k = list(map(int,input().split()))
    l = list(map(int,input().split()))
    OUT = [n // 2] * (2 * k + 2)
    extraL = [0] * (2 * k + 2)
    extraR = [0] * (2 * k + 2)
    for i in range(n//2):
        left = l[i]
        right = l[n - 1 - i]
        OUT[left + right] -= 1
        extraL[min(left,right)] += 1
        extraR[max(left,right) + k + 1] += 1

    curr = 0
    for i in range(2 * k + 2):
        curr += extraR[i]
        extraR[i] = curr

    curr = 0
    for i in range(2 * k + 1, -1, -1):
        curr += extraL[i]
        extraL[i] = curr
        
    for i in range(2 * k + 2):
        OUT[i] += extraL[i] + extraR[i]

    print(min(OUT))
            


A = [0 for x in range(400005)]
t = int(input())
def mymin(a,b):
    if(a<b):
        return a
    else:
        return b

def mymax(a,b):
    if(a>b):
        return a
    else:
        return b

for tests in range(t):
    [n,k] = input().split()
    n = int(n)
    k = int(k)
    B = input().split()
    for i in range(2,(2*k)+1):
        A[i] = 0
    n2 = int(n/2)
    for i in range(n2):
        B[i] = int(B[i])
        B[n-1-i] = int(B[n-1-i])
        mi = mymin(B[i],B[n-1-i])
        ma = mymax(B[i],B[n-1-i])
        A[2] += 2
        A[mi+1] -= 1
        A[mi+ma] -= 1
        if(mi+ma+1 <= 2*k):
            A[mi+ma+1] +=1
        if(ma+k+1 <= 2*k):
            A[ma+k+1] +=1
    ans = n
    for i in range(2,(2*k)+1):
        A[i] += A[i-1]
        if(A[i]<ans):
            ans = A[i]
    print(ans)