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:
#!/usr/bin/env pypy3

def swaps(A):
    # assume A is a permutation of range(0, len(A))

    ret = []

    for k in range(len(A)-1, 1, -1):
        assert(A.index(k) <= k)
        # print(f"putting {k} in the correct position")
        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]
            # print(f"A={A}")

    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]

    # if A2 is None:
    #     print(f"A={A}")
    # else:
    #     print(f"A={A} A2={A2}")

    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)