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.*;
import java.math.*;
import java.util.*;
 
public class Main {
	static final long MOD = 1000000007L;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		
		int Q = sc.ni();
		for (int q = 0; q < Q; q++) {
			int N = sc.ni();
			int[] nums = new int[N];
			int[] cnt = new int[500];
			for (int i = 0; i < N; i++) {
				int n = sc.ni()-1;
				nums[i] = 500*n+cnt[n];
				cnt[n] += 1;
			}
			int swap1 = -1;
			int swap2 = -1;
			loop:
			for (int i = 0; i < N; i++) {
				for (int j = i+1; j < N; j++) {
					if (nums[i]/500 == nums[j]/500) {
						swap1 = i;
						swap2 = j;
						break loop;
					}
				}
			}
			
			//nums is guaranteed to only have distinct elements at this point
			boolean good = false;
			ArrayList<Integer> ans1 = solve(nums);
			if (ans1.isEmpty() || ans1.get(0)!=-1) {
				good = true;
				pw.println(ans1.size());
				for (int a: ans1)
					pw.print(a + " ");
				pw.println();
			}
			if (!good && swap1 >= 0) {
				int temp = nums[swap1];
				nums[swap1] = nums[swap2];
				nums[swap2] = temp;
				ArrayList<Integer> ans2 = solve(nums);
				if (ans2.isEmpty() || ans2.get(0) != -1) {
					good = true;
					pw.println(ans2.size());
					for (int a: ans2)
						pw.print(a + " ");
					pw.println();
				}
			}
			if (!good) {
				pw.println(-1);
			}
		}
		pw.close();
	}
	
	public static ArrayList<Integer> solve(int[] n) {
		int N = n.length;
		int[] nums = Arrays.copyOf(n, N);
		int[] sorted = Arrays.copyOf(nums, N);
		Arrays.sort(sorted);
		
		int index = N-1;
		ArrayList<Integer> moves = new ArrayList<Integer>();
		int cur = -1;
		int old = N;
		while (true) {
			while (index >= 2 && sorted[index]==nums[index]) {
				index--;
			}
			if (index < 2) break;
			if (old != index) {
				cur = -1;
				for (int i = 0; i <= index; i++) {
					if (nums[i]==sorted[index]) {
						cur = i;
						break;
					}
				}
				old = index;
			}
			
			if (cur==0) {
				moves.add(1);
				int temp = nums[0];
				nums[0] = nums[2];
				nums[2] = nums[1];
				nums[1] = temp;
				cur++;
			} else {
				moves.add(cur);
				int temp = nums[cur-1];
				nums[cur-1] = nums[cur+1];
				nums[cur+1] = nums[cur];
				nums[cur] = temp;
				cur++;
			}
		}
		
		boolean good = true;
		for (int i = 0; i < N; i++) {
			if (sorted[i] != nums[i]) {
				good = false;
				break;
			}
		}
		
		if (good) {
			return moves;
		} else {
			ArrayList<Integer> bad = new ArrayList<Integer>();
			bad.add(-1);
			return bad;
		}
	}
	
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        }
        
        int ni() { 
            return Integer.parseInt(next()); 
        }
  
        long nl() { 
            return Long.parseLong(next()); 
        } 
  
        double nd() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() {
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str;
        }
    }
}