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

Solution:


import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

public class C636D {
	static PrintWriter output;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		output = new PrintWriter(System.out);
		int tests = sc.nextInt();
		for (int i=0; i<tests ;i++) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			int[] arr = new int[n];
			for (int j=0; j<n; j++) {
				arr[j] = sc.nextInt();
			}
			solve(arr, k);
		}
		sc.close();
		output.close();
	}

	private static void solve(int[] arr, int k) {
		int[] minCounts = new int[k+1];
		int[] maxCounts = new int[k+1];

		PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<List<Integer>>(new Comparator<List<Integer>> () {
			public int compare(List<Integer> o1, List<Integer> o2) {
				if (o2.get(1) == o1.get(1)) {
					return o2.get(0).compareTo(o1.get(0));
				}
				return o2.get(1).compareTo(o1.get(1));
			}
		});
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i=0; i<arr.length/2; i++) {
			int n = arr[i] + arr[arr.length-i-1];
			int min = Math.min(arr[i], arr[arr.length-i-1]); // the minimum which can NOT be created with this pair of digits with one operation
			int max = Math.max(arr[i], arr[arr.length-i-1]) + k + 1; // the maximum which can NOT be created with this pair of digits with one operation
			minCounts[min-1]++; //shifting index by 1
			maxCounts[max - k - 1]++; //this number will always be greater than (k+1), so we shifting the index to 0 base
			map.put(n, map.getOrDefault(n, 0) + 1);
		}
		
		for (int i=minCounts.length-1; i>0; i--) {
			minCounts[i-1] += minCounts[i];
		}
		for (int i=0; i<minCounts.length-1; i++) {
			maxCounts[i+1] += maxCounts[i];
		}

		for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
			maxHeap.add(Arrays.asList(entry.getKey(), entry.getValue()));
		}
		
		int result = arr.length/2;
		while (!maxHeap.isEmpty()) {
			List<Integer> l = maxHeap.poll();
			int tmpResult = arr.length/2 - l.get(1);
			if (l.get(0) <= k) {
				tmpResult += minCounts[l.get(0)-1];
			}
			if (l.get(0) > k) {
				tmpResult += maxCounts[l.get(0)-k-1];
			}
			if (tmpResult < result)
				result = tmpResult;
		}
		
		if (result > arr.length/2) result = arr.length/2;
		output.write(result + "\n");
	}
}