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