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.util.*;
import java.io.*;
public class f {
	static final FS sc = new FS();
	static final PrintWriter pw = new PrintWriter(System.out);
	
	static final int max = 500;
	
	static int n;
	static int[] arr, idx;
	static ArrayList<Integer> steps;
	public static void main(String[] args) {
		int t = sc.nextInt();
		scan : for(int tt = 1; tt <= t; ++tt) {
			n = sc.nextInt();
			num[] nums = new num[n];
			for(int i = 0; i < n; ++i) {
				int in = sc.nextInt();
				nums[i] = new num(in, i);
			}
			
			Arrays.sort(nums);
			if(solve(nums)) continue scan;
			else {
				// then switch the first two things that are the same value
				for(int i = 0; i < n - 1; ++i) {
					if(nums[i].val == nums[i + 1].val) {
						// switch these two
						num num1 = new num(nums[i].val, nums[i].idx);
						num num2 = new num(nums[i + 1].val, nums[i + 1].idx);
						
						nums[i] = new num(num2.val, num2.idx);
						nums[i + 1] = new num(num1.val, num1.idx);
						
						solve(nums);
						continue scan;
					}
				}
			}
			
			pw.println(-1);
		}
		pw.flush();
	}
	static boolean solve(num[] nums) {
		arr = new int[n + 1];
		for(int i = 0; i < n; ++i) arr[nums[i].idx + 1] = i + 1;
		idx = new int[n + 1];
		for(int i = 1; i <= n; ++i) idx[arr[i]] = i;
		
		steps = new ArrayList<>();
		for(int a = 1; a <= n - 2; ++a) {
			int i = idx[a];
			
			// move this thing
			while(i >= a + 2) {
				// do a cyclic shift
				shift(i - 2);
				i -= 2;
			}
			
			// we in a weird spot
			if(i >= a + 1) {
				shift(i - 1);
				shift(i - 1);
			}
		}
		
		if(arr[n - 1] < arr[n]) {
			// weGood; print
			pw.println(steps.size());
			for(int a : steps) pw.print(a + " ");
			pw.println();
			return true;
		}
		
		return false;
	}
	static void shift(int i) {
		int temp = arr[i + 2];
		arr[i + 2] = arr[i + 1];
		arr[i + 1] = arr[i];
		arr[i] = temp;
		
		for(int j = i; j <= i + 2; ++j) {
			idx[arr[j]] = j;
		}
		
		steps.add(i);
	}
	static class num implements Comparable<num>{
		int val, idx;
		num(int vv, int ii){
			val = vv;
			idx = ii;
		}
		public int compareTo(num in) {
			if(val != in.val) return Integer.compare(val, in.val);
			return Integer.compare(idx, in.idx);
		}
	}
	static class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while(!st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(Exception e) {}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}