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:
t = int(input())
from copy import deepcopy

def solve():
    d = [-1]*n
    for i in range(n):
        x,y = l2[i]
        d[y] = i
    ans = []
    count = 0
    for i in range(n-1,1,-1):
        y = d.index(i)
        
        while y < i:
            count += 1
            if y == i-1:
                ans.append(y)
                d[y-1],d[y],d[y+1] = d[y+1],d[y-1],d[y]    
            else:
                ans.append(y+1)
                d[y],d[y+1],d[y+2] = d[y+2],d[y],d[y+1]
            y += 1
    
    if d[0] <= d[1] <= d[2]:
        print(count)
        print(*ans)
        return True
    else:
        check = False
        c = 0
        while c < 3:
            ans.append(1)
            d[0],d[1],d[2] = d[2],d[0],d[1]
            count += 1
            c += 1
            if d[0] <= d[1] <= d[2]:
                check = True
                break
        if check:
            print(count)
            print(*ans)
            return True
        else:
            return False

for _ in range(t):
    n = int(input())
    l = list(map(int,input().split()))
    l2 = sorted([[x,i] for i,x in enumerate(l)])

    if solve() == False:
        for i in range(n-1):
            if l2[i][0] == l2[i+1][0]:
                l2[i][1],l2[i+1][1] = l2[i+1][1],l2[i][1]
                break
        if solve() == False:
            print(-1)