Problem: You are given an array a consisting of n integers.

In one move, you can choose some index i (1 ≤ i ≤ n - 2) and shift the segment [a_i, a_{i + 1}, a_{i + 2}] cyclically to the right (i.e. replace the segment [a_i, a_{i + 1}, a_{i + 2}] with [a_{i + 2}, a_i, a_{i + 1}]). 

Your task is to sort the initial array by no more than n^2 such operations or say that it is impossible to do that.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (3 ≤ n ≤ 500) — the length of a. The second line of the test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 500), where a_i is the i-th element a.

It is guaranteed that the sum of n does not exceed 500.

Output

For each test case, print the answer: -1 on the only line if it is impossible to sort the given array using operations described in the problem statement, or the number of operations ans on the first line and ans integers idx_1, idx_2, ..., idx_{ans} (1 ≤ idx_i ≤ n - 2), where idx_i is the index of left border of the segment for the i-th operation. You should print indices in order of performing operations.

Example

Input


5
5
1 2 3 4 5
5
5 4 3 2 1
8
8 4 5 2 3 6 7 3
7
5 2 1 6 4 7 3
6
1 2 3 3 6 4


Output


0

6
3 1 3 2 2 3 
13
2 1 1 6 4 2 4 3 3 4 4 6 6 
-1
4
3 3 4 4 

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main implements Runnable {
	boolean oj = false;
	Reader scn;
	PrintWriter out;
	String INPUT = "";

	void solve() {
		int t = scn.nextInt();
		while(t-- > 0) {
			int n = scn.nextInt();
			int[][] arr = new int[n][2], need = new int[n][2], copy = new int[n][2];
			
			for(int i = 0; i < n; i++) {
				copy[i][0] = need[i][0] = arr[i][0] = scn.nextInt();
				need[i][1] = i + 1;
				copy[i][1] = arr[i][1] = -(i + 1);
			}
			
			Arrays.sort(need, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(arr[j][1] > 0) {
						continue;
					}
					if(arr[j][0] == need[i][0] && need[i][1] + arr[j][1] == 0) {
						arr[j][1] = i;
					}
				}
			}
			
			StringBuilder sb = new StringBuilder();
			int ans = 0;
			for(int i = 0; i < n; i++) {
				if(arr[i][1] == i) {
					continue;
				}
				int pos = -1;
				for(int j = 0; j < n; j++) {
					if(arr[j][1] == i) {
						pos = j;
					}
				}
				
				assert pos > i;
				if(pos == i + 1) {
					if(i == n - 2) {
						ans = -1;
						break;
					}
					rotate(arr, i);
					rotate(arr, i);
					sb.append(i + 1 + " ");
					sb.append(i + 1 + " ");
					ans += 2;
				} else {
					while(pos > i + 1) {
						rotate(arr, pos - 2);
						sb.append(pos - 1 + " ");
						pos = pos - 2;
						ans++;
					}
					if(pos != i) {
						rotate(arr, i);
						rotate(arr, i);
						sb.append(i + 1 + " ");
						sb.append(i + 1 + " ");
						ans += 2;
					}
				}
			}
			
			if(ans != -1) {
				assert ans <= n * n;
				out.println(ans);
				out.println(sb);
				continue;
			}
			
			boolean found = false;
			for(int i = n - 1; i > 0; i--) {
				if(need[i][0] == need[i - 1][0]) {
					int temp = need[i][1];
					need[i][1] = need[i - 1][1];
					need[i - 1][1] = temp;
					found = true;
					break;
				}
			}
			if(!found) {
				out.println(-1);
				continue;
			}
			
			for(int i = 0; i < n; i++) {
				arr[i][0] = copy[i][0];
				arr[i][1] = copy[i][1];
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(arr[j][1] > 0) {
						continue;
					}
					if(arr[j][0] == need[i][0] && need[i][1] + arr[j][1] == 0) {
						arr[j][1] = i;
					}
				}
			}
			
			sb = new StringBuilder();
			ans = 0;
			for(int i = 0; i < n; i++) {
				if(arr[i][1] == i) {
					continue;
				}
				int pos = -1;
				for(int j = 0; j < n; j++) {
					if(arr[j][1] == i) {
						pos = j;
					}
				}
				
				assert pos > i;
				if(pos == i + 1) {
					if(i == n - 2) {
						ans = -1;
						break;
					}
					rotate(arr, i);
					rotate(arr, i);
					sb.append(i + 1 + " ");
					sb.append(i + 1 + " ");
					ans += 2;
				} else {
					while(pos > i + 1) {
						rotate(arr, pos - 2);
						sb.append(pos - 1 + " ");
						pos = pos - 2;
						ans++;
					}
					if(pos != i) {
						rotate(arr, i);
						rotate(arr, i);
						sb.append(i + 1 + " ");
						sb.append(i + 1 + " ");
						ans += 2;
					}
				}
			}
			
			if(ans != -1) {
				assert ans <= n * n;
				out.println(ans);
				out.println(sb);
			} else {
				out.println(-1);
			}
		}
	}
	
	void rotate(int[][] arr, int pos) {
		int[] temp = arr[pos + 2];
		arr[pos + 2] = arr[pos + 1];
		arr[pos + 1] = arr[pos];
		arr[pos] = temp;
	}

	public void run() {
		long time = System.currentTimeMillis();
		boolean judge = System.getProperty("ONLINE_JUDGE") != null || oj;
		out = new PrintWriter(System.out);
		scn = new Reader(judge);
		solve();
		out.flush();
		if (!judge) {
			System.out.println(Arrays.deepToString(new Object[] { System.currentTimeMillis() - time + " ms" }));
		}
	}

	public static void main(String[] args) {
		new Thread(null, new Main(), "Main", 1 << 28).start();
	}

	class Reader {
		InputStream is;

		public Reader(boolean oj) {
			is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		}

		byte[] inbuf = new byte[1024];
		public int lenbuf = 0, ptrbuf = 0;

		int readByte() {
			if (lenbuf == -1)
				throw new InputMismatchException();
			if (ptrbuf >= lenbuf) {
				ptrbuf = 0;
				try {
					lenbuf = is.read(inbuf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return -1;
			}
			return inbuf[ptrbuf++];
		}

		boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}

		int skip() {
			int b;
			while ((b = readByte()) != -1 && isSpaceChar(b))
				;
			return b;
		}

		String next() {
			int b = skip();
			StringBuilder stringB = new StringBuilder();
			while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
				stringB.appendCodePoint(b);
				b = readByte();
			}
			return stringB.toString();
		}

		String nextLine() {
			int b = skip();
			StringBuilder stringB = new StringBuilder();
			while ((!isSpaceChar(b) || b == ' ')) { // when nextLine, (isSpaceChar(b) && b != ' ')
				stringB.appendCodePoint(b);
				b = readByte();
			}
			return stringB.toString();
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		char nextChar() {
			return (char) skip();
		}

		char[] next(int n) {
			char[] buff = new char[n];
			int b = skip(), p = 0;
			while (p < n && !(isSpaceChar(b))) {
				buff[p++] = (char) b;
				b = readByte();
			}
			return n == p ? buff : Arrays.copyOf(buff, p);
		}

		int nextInt() {
			int num = 0, b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}

			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}

		long nextLong() {
			long num = 0;
			int b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}

			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}

		long[] nextLongArr(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		int[] nextIntArr(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		char[][] nextMat(int n, int m) {
			char[][] map = new char[n][];
			for (int i = 0; i < n; i++)
				map[i] = next(m);
			return map;
		}

		long[][] next2Long(int n, int m) {
			long[][] arr = new long[n][];
			for (int i = 0; i < n; i++) {
				arr[i] = nextLongArr(m);
			}
			return arr;
		}

		int[][] next2Int(int n, int m) {
			int[][] arr = new int[n][];
			for (int i = 0; i < n; i++) {
				arr[i] = nextIntArr(m);
			}
			return arr;
		}

		long[] shuffle(long[] arr) {
			Random r = new Random();
			for (int i = 1, j; i < arr.length; i++) {
				j = r.nextInt(i);
				arr[i] = arr[i] ^ arr[j];
				arr[j] = arr[i] ^ arr[j];
				arr[i] = arr[i] ^ arr[j];
			}
			return arr;
		}

		int[] shuffle(int[] arr) {
			Random r = new Random();
			for (int i = 1, j; i < arr.length; i++) {
				j = r.nextInt(i);
				arr[i] = arr[i] ^ arr[j];
				arr[j] = arr[i] ^ arr[j];
				arr[i] = arr[i] ^ arr[j];
			}
			return arr;
		}

		long[] uniq(long[] arr) {
			arr = scn.shuffle(arr);
			Arrays.parallelSort(arr);
			long[] rv = new long[arr.length];
			int pos = 0;
			rv[pos++] = arr[0];
			for (int i = 1; i < arr.length; i++) {
				if (arr[i] != arr[i - 1]) {
					rv[pos++] = arr[i];
				}
			}
			return Arrays.copyOf(rv, pos);
		}

		int[] uniq(int[] arr) {
			arr = scn.shuffle(arr);
			Arrays.parallelSort(arr);
			int[] rv = new int[arr.length];
			int pos = 0;
			rv[pos++] = arr[0];
			for (int i = 1; i < arr.length; i++) {
				if (arr[i] != arr[i - 1]) {
					rv[pos++] = arr[i];
				}
			}
			return Arrays.copyOf(rv, pos);
		}

		long[] reverse(long[] arr) {
			int i = 0, j = arr.length - 1;
			while (i < j) {
				arr[i] = arr[i] ^ arr[j];
				arr[j] = arr[i] ^ arr[j];
				arr[i] = arr[i] ^ arr[j];
				i++;
				j--;
			}
			return arr;
		}

		int[] reverse(int[] arr) {
			int i = 0, j = arr.length - 1;
			while (i < j) {
				arr[i] = arr[i] ^ arr[j];
				arr[j] = arr[i] ^ arr[j];
				arr[i] = arr[i] ^ arr[j];
				i++;
				j--;
			}
			return arr;
		}

		long[] compres(long[] arr) {
			int n = arr.length;
			long[] rv = Arrays.copyOf(arr, n);
			rv = uniq(rv);
			for (int i = 0; i < n; i++) {
				arr[i] = Arrays.binarySearch(rv, arr[i]);
			}
			return arr;
		}

		int[] compres(int[] arr) {
			int n = arr.length;
			int[] rv = Arrays.copyOf(arr, n);
			rv = uniq(rv);
			for (int i = 0; i < n; i++) {
				arr[i] = Arrays.binarySearch(rv, arr[i]);
			}
			return arr;
		}

		void deepFillLong(Object array, long val) {
			if (!array.getClass().isArray()) {
				throw new IllegalArgumentException();
			}
			if (array instanceof long[]) {
				long[] intArray = (long[]) array;
				Arrays.fill(intArray, val);
			} else {
				Object[] objArray = (Object[]) array;
				for (Object obj : objArray) {
					deepFillLong(obj, val);
				}
			}
		}

		void deepFillInt(Object array, int val) {
			if (!array.getClass().isArray()) {
				throw new IllegalArgumentException();
			}
			if (array instanceof int[]) {
				int[] intArray = (int[]) array;
				Arrays.fill(intArray, val);
			} else {
				Object[] objArray = (Object[]) array;
				for (Object obj : objArray) {
					deepFillInt(obj, val);
				}
			}
		}

		void tr(Object... o) {
			if (!oj)
				System.out.println(Arrays.deepToString(o));
		}
	}
}