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 io
import os
from collections import Counter, deque

DEBUG = False


def solve(N, A):
    original = list(A)
    sortedA = sorted(A)
    if N <= 5:
        # Bruteforce for small N

        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:
        # Larger N should be fine since fixing each element only cost N / 2 + small
        moves = []
        for i, target in enumerate(sortedA):
            # A is unsorted portion, find target and move it to i
            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 + 1:
                # current array looks like:
                # sortedA[:i] + [A[0], target] + A[1:]
                assert len(A) > 0
                if len(A) >= 2:
                    # Rotate twice:
                    # A[0], target, A[1]
                    # A[1], A[0], target
                    # target, A[1], A[0]
                    moves.append(i)
                    moves.append(i)
                    A[0], A[1] = A[1], A[0]
                else:
                    assert len(A) == 1
                    # Last two elements are A[0] and target
                    if A[0] == target:
                        # Already good
                        break
                    if sortedA[i - 1] == target:
                        # sortedA[i-1], A[0], target
                        # target, sortedA[i-1], A[0]
                        moves.append(i - 1)
                        break
                    assert sortedA[i - 1] < target < A[0]

                    # Otherwise can only be fixed if we have duplicates somewhere?

                    dupes = set(k for k, v in Counter(sortedA).items() if v > 1)
                    if not dupes:
                        return -1

                    # want N - 2 so need to break parity
                    assert j == N - 1

                    while sortedA[j - 1] not in dupes:
                        # Target is dragged by 2 until it hit dupes (which are always next to each other so can't be missed)
                        moves.append(j - 2)
                        j -= 2

                    assert sortedA[j - 1] in dupes

                    if sortedA[j] in dupes:
                        # moved target to in between j-1 and j
                        # dupe, target, dupe
                        # dupe, dupe, target
                        moves.append(j - 1)
                        j += 1
                    else:
                        assert sortedA[j - 2] in dupes
                        # dupe, dupe, target
                        # target, dupe, dupe
                        # dupe, target, dupe
                        moves.append(j - 2)
                        moves.append(j - 2)
                        j -= 1
                    # Broke parity of j, move it back to the end
                    while j != N - 2:
                        moves.append(j)
                        moves.append(j)
                        j += 2
                    break

            # print(sortedA[: i + 1], A)
    if DEBUG:
        # Sanity check
        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()

if __name__ == "__main__":
    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)