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.util.*;

public class r636p4 {

    private static int n, k;
    private static long res[];
    private static int inp[];
    private static Node root;

    static class Node{

        int begin, end;
        Node left, right;
        int data, lazy;
        
        Node(int b, int e){
            begin = b;
            end = e;
            data = 0;
            lazy = 0;

            if(begin != end){
                left = new Node(begin, (begin+end)/2);
                right = new Node((begin+end)/2+1, end);
            }
        }

        void set(int l, int r, int val){
            if(l<0 || r<0 || l > 2*k || r > 2*k || l>r || l>end || begin>r) return;

            if(l <= begin && end <= r){
                if(begin != end)
                    lazy += val;
                else
                    data += val;
                //pw.println(+begin+" "+end+" "+l+" "+r+" "+val);
                return;
            }

            if(lazy != 0){
                left.set(begin, (begin+end)/2, lazy);
                right.set((begin+end)/2+1, end, lazy);
                lazy = 0;
            }

            left.set(l, r, val);
            right.set(l, r, val);
        }

        void genRes(){
            if(begin != end){
                left.lazy += lazy;
                right.lazy += lazy;
                lazy = 0;
                left.genRes();
                right.genRes();
            }
            else{
                data += lazy;
                res[begin] = data;
            }
        }
    }

    private static void input()throws IOException{
        n = nextInt();
        k = nextInt();
        inp = intArray(n);
        res = new long[2*k+1];
    }

    private static void cal(){
        root = new Node(0, 2*k);
        for(int i=0; i<n/2; i++){
            int min = Math.min(inp[i], inp[n-i-1]), max = Math.max(inp[i], inp[n-i-1]), sum = inp[i]+inp[n-i-1];
            root.set(2, min, 2);
            root.set(min+1, sum-1, 1);
            //root.set(sum, sum, 0);
            root.set(sum+1, max+k, 1);
            root.set(max+k+1, 2*k, 2);
        }

        root.genRes();
        long min = Integer.MAX_VALUE;
        for(int i=2; i<=2*k; i++){
            min = Math.min(min, res[i]);
            //pw.print(+res[i]+" ");
        }
    
        //pw.println("\n"+min);

        pw.println(+min);
    }

    private static void solve()throws IOException{
        input();
        cal();
    }

    private static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tk;
    private static PrintWriter pw = new PrintWriter(System.out);

    private static void next()throws IOException{
        if(tk == null || !tk.hasMoreTokens())   
            tk = new StringTokenizer(r.readLine());
    }

    private static int nextInt()throws IOException{
        next();
        return Integer.parseInt(tk.nextToken());
    }

    private static long nextLong()throws IOException{
        next();
        return Long.parseLong(tk.nextToken());
    }

    private static String readString()throws IOException{
        next();
        return tk.nextToken();
    }

    private static double nextDouble()throws IOException{
        next();
        return Double.parseDouble(tk.nextToken());
    }

    private static int[] intArray(int n)throws IOException{
        next();
        int arr[] = new int[n];

        for(int i=0; i<n; i++)
            arr[i] = nextInt();

        return arr;
    }

    private static long[] longArray(int n)throws IOException{
        next();
        long arr[] = new long[n];

        for(int i=0; i<n; i++)
            arr[i] = nextLong();

        return arr;
    }

    public static void main(String args[])throws IOException{

        int t = nextInt();
        while(t-->0)
            solve();

        pw.flush();
        pw.close();
    }
}