Problem: You are given an array a consisting of n integers.

In one move, you can choose some index i (1 ≤ i ≤ 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 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (3 ≤ n ≤ 500) — the length of a. The second line of the test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 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, ..., idx_{ans} (1 ≤ idx_i ≤ 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 

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 False and N <= 5:
        # Bruteforce for small N (Turns out I didn't need this case)

        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
            # print(sortedA[: i], A)
            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

            # 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]
                continue
            assert len(A) == 1

            # Unsorted is just 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]

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

            # 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

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

    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)