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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class F {

	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Solution sol = new Solution();
		int t = in.ni();
		for (int i = 0; i < t; ++i)
			sol.solve(in, out);
		out.close();
	}

	private static final boolean debug = false;

	private static class Solution {
		private void solve(InputReader in, PrintWriter out) {
			int n = in.ni();
			Element[] elements = new Element[n], sorted = new Element[n];
			for (int i = 0; i < n; ++i)
				elements[i] = sorted[i] = new Element(in.ni());
			Arrays.sort(sorted);
			for (int i = 0; i < n; ++i)
				sorted[i].value = i;
			int invs = 0;
			for (int i = 0; i < n; ++i)
				for (int j = i + 1; j < n; ++j)
					if (elements[i].value > elements[j].value)
						++invs;
			if (debug)
				System.out.println("Initial inverstions: " + invs);
			if (invs % 2 == 1) {
				outer: for (int first = 0; first < n; ++first) {
					for (int second = first + 1; second < n; ++second) {
						if (elements[first].orig != elements[second].orig)
							continue;
						int changed = 0;
						for (int i = first; i < second; ++i)
							if (elements[i].value >= elements[first].value
									&& elements[i].value < elements[second].value)
								++changed;
						if (changed % 2 == 1) {
							++invs;
							int temp = elements[first].value;
							elements[first].value = elements[second].value;
							elements[second].value = temp;
							break outer;
						}
					}
				}
			}
			Arrays.sort(sorted);
			if (debug)
				System.out.println("Perm:");
			for (Element e : elements)
				if (debug)
					System.out.print(e.value + " ");
			if (debug)
				System.out.println();

			if (invs % 2 != 0) {
				out.println(-1);
				return;
			}
			List<Integer> indecies = new ArrayList<>();
			for (int toFixInd = n - 1; toFixInd >= 0; --toFixInd) {
				Element toFix = sorted[toFixInd];
				int index = 0;
				for (int i = 0; i < n; ++i)
					if (elements[i] == toFix)
						index = i;
				if (debug)
					System.out.println("Trying to fix thing at index " + index);
				while (index < toFixInd - 1) {
					swap(elements, index, indecies);
					++index;
				}
				if (index == toFixInd - 1) {
					swap(elements, toFixInd - 2, indecies);
					++index;
				}
			}
			out.println(indecies.size());
			for (int i : indecies) {
				out.print(i + 1 + " ");
			}
			out.println();
		}

		private void swap(Element[] elements, int index, List<Integer> indecies) {
			if (debug) System.out.println("Swapping from index "+index);
			indecies.add(index);
			Element e1 = elements[index], e2 = elements[index + 1], e3 = elements[index + 2];
			elements[index] = e3;
			elements[index + 1] = e1;
			elements[index + 2] = e2;
		}
	}

	private static class Element implements Comparable<Element> {
		int value, orig;

		public Element(int orig) {
			this.value = this.orig = orig;
		}

		@Override
		public int compareTo(Element o) {
			return Integer.compare(value, o.value);
		}
	}

	private static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		private InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		private String n() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		private int ni() {
			return Integer.parseInt(n());
		}

		private long nl() {
			return Long.parseLong(n());
		}

		private int[] readArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; ++i)
				a[i] = ni();
			return a;
		}
	}

}