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.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;

import static java.lang.Math.abs;
import static java.lang.Math.ceil;

/* tutorial solution much better*/
public class Main {
    public static int dirr[][] = {{1,0},{0,1},{0,-1},{-1,0}};
    public static boolean possible;
    public static void main(String[] args) {
	// write your code here
      //  q1365D();
       // q1354D();
      //  q1363C();
      //  q545C();
       // q1361A();
       // q1359C();
        q1343D();
    }
    public static void q1343D(){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i=0;i<t;i++){
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] arr = new int[n];
            int[] pref = new int[2*k+2];
            int[] cnt = new int[2*k+2];
            for(int j=0;j<n;j++){
                arr[j]=sc.nextInt();
            }
            for(int j=0;j<n/2;j++){
                int maxi=Math.max(arr[j],arr[n-j-1])+k;
                int mini = Math.min(arr[j],arr[n-j-1])+1;
                pref[maxi+1]--;
                pref[mini]++;
                cnt[arr[j]+arr[n-j-1]]++;
            }
            for(int j=1;j<2*k+1;j++){
                pref[j]+=pref[j-1];
            }
            int mini =n;
            for(int j=2;j<=2*k;j++){
                mini = Math.min(mini,n-pref[j]-cnt[j]);
            }
            System.out.println(mini);
        }
    }

    public static void q1359C(){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i=0;i<t;i++){
            double h = sc.nextInt();
            double c = sc.nextInt();
            double temp = sc.nextInt();
            if((h+c)==2*temp){
                System.out.println("2");
            }
            else {
                Double k = (h-temp)/(2*temp-h-c);
                if(k<0){
                    System.out.println("2");
                    continue;
                }
                Integer k1 = k.intValue()+1;
              //  System.out.println(k);
                double p = abs((k.intValue()*(h+c)+h)-temp*(2*k.intValue()+1))*(2*k.intValue()+3);
                double q =  abs(((k.intValue()+1)*(h+c)+h)-temp*(2*k.intValue()+3))*(2*k.intValue()+1);
              //  System.out.println(p+" "+q);
                if(p<=q){
                    System.out.println(k.intValue()*2+1);
                }
                else {
                    System.out.println(k1.intValue()*2+1);
                }
            }
        }

    }
    public static void q1361A(){
        Scanner sc = new Scanner(System.in);
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        ArrayList<ArrayList<Integer>> occur = new ArrayList<>();
        for(int i=0;i<=1000000;i++){
            adj.add(new ArrayList<>());
            occur.add(new ArrayList<>());
        }
        int[] color = new int[1000000];
        int n = sc.nextInt();
        int m = sc.nextInt();


        for(int i=0;i<m;i++){
            int c = sc.nextInt();
            int d = sc.nextInt();
            adj.get(c).add(d);
            adj.get(d).add(c);
        }
        for(int i=0;i<n;i++){
            int temp = sc.nextInt();
            occur.get(temp).add(i+1);
            color[i+1] = temp;
            if(temp > n){
                System.out.println("-1");
                return;
            }
        }
        ArrayList<Integer> ans = new ArrayList<>();
        int[] temp = new int[n+1];
        for(int i=1;i<=n;i++){
            for(Integer p:occur.get(i)){
                int cnt =i-1;
                for(Integer q: adj.get(p)){
                    if(color[q]==i){
                        System.out.println("-1");
                        return;
                    }
                    else if(color[q]<i){
                        if(temp[color[q]]!=p) {
                            temp[color[q]] = p;
                            cnt--;
                        }
                    }
                }
                if(cnt!=0){
                    System.out.println("-1");
                    return;
                }
                //System.out.print(" "+p);
                ans.add(p);
            }

        }
        for(int i=0;i<ans.size()-1;i++){
            System.out.print(ans.get(i)+" ");
        }
        System.out.print(ans.get(ans.size()-1));
    }
    public static void q545C(){
        Scanner sc = new Scanner(System.in);

            List<Corrd> arr = new ArrayList<>();
            int n = sc.nextInt();
            int ans=n-2<=0?n:2;
            for(int j=0;j<n;j++){
                arr.add(new Corrd(sc.nextInt(),sc.nextInt()));
            }
            int closest = arr.get(0).x;
            for(int j=1;j<arr.size()-1;j++){
                Corrd tree = arr.get(j);
                int farthest = arr.get(j+1).x;
                if(closest<tree.x-tree.y){
                    ans++;
                    closest=tree.x;
                }
                else if(farthest>tree.x+tree.y){
                    ans++;
                    closest=tree.x+tree.y;
                }
                else{
                    closest= tree.x;
                }
            }
            System.out.println(ans);

    }

    public static void q1363C(){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i=0;i<t;i++){
            int deg =0;
            int n = sc.nextInt();
            int x = sc.nextInt();
            for(int j=0;j<n-1;j++){
                int p = sc.nextInt();
                int q = sc.nextInt();
                if(p==x || q==x){
                    deg++;
                }
            }
            if(deg<=1){

                System.out.println("Ayush");
            }
            else{
                if(n%2==0){
                    System.out.println("Ayush");
                }
                else{
                    System.out.println("Ashish");
                }
            }
        }
    }

    public static void q1354D(){

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] cnt= new int[n+1];
        for(int i=0;i<n;i++){
            cnt[sc.nextInt()]++;
        }
        for(int i=0;i<q;i++){
            int k = sc.nextInt();
            if(k>0){
                cnt[k]++;
            }
            else{
                k=k*(-1);
            }
        }
    }

    public static void q1365D(){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i=0;i<t;i++){
            possible = true;
            int n = sc.nextInt();
            int m = sc.nextInt();
            Integer[][] graph = new Integer[n+1][m+1];
            Corrd[][] corrds = new Corrd[n+1][m+1];

            for(int j=0;j<n;j++){
                String str = sc.next();

                for(int k=0;k<m;k++){
                    graph[j][k] = (int)str.charAt(k);
                  //  System.out.println(graph[j][k]);
                    corrds[j][k] = new Corrd(j,k);
                }
            }
            dfs(n-1,m-1,n,m,graph,corrds);
            if(!possible){
                System.out.println("NO");
                continue;
            }

            dfs2(n-1,m-1,n,m,graph,corrds);
            for(int j=0;j<n;j++){
                for(int k=0;k<m;k++){
                  //  System.out.print((char)((int)graph[j][k]));
                    if(graph[j][k]=='G'){
                      //  System.out.print(corrds[j][k].color);
                        if(corrds[j][k].color<2){
                         //   System.out.print("Mee"+corrds[j][k].color);
                            possible = false;
                            break;
                        }
                    }
                }
               // System.out.println();
            }
            System.out.println(possible?"YES":"NO");
        }
    }
    public static void dfs(int x,int y,int maxx,int maxy,Integer[][] graph,Corrd[][] corrds) {
        Stack<Corrd> st = new Stack<Corrd>();
        if (graph[x][y] == '#') {
            return;
        }
        st.push(corrds[x][y]);
        corrds[x][y].color++;
        while (!st.empty()) {
            Corrd p = st.pop();
          //  System.out.println(p.x + " " + p.y);
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dirr[i][0];
                int ny = p.y + dirr[i][1];
                if (nx >= 0 && nx < maxx && ny >= 0 && ny < maxy && corrds[nx][ny].color == 0) {
                  //  System.out.println("x" + nx + " " + ny);
                    if (!(graph[nx][ny] == '#')) {
                        if (graph[nx][ny] == 'B' && (graph[p.x][p.y] == '.')) {
                            graph[p.x][p.y] = (int) '#';
                            break;
                        }
                        else {
                            if (graph[nx][ny] == 'B' && graph[p.x][p.y] == 'G') {
                                possible = false;
                                break;
                            }
                            else {
                                corrds[nx][ny].color++;
                                st.push(corrds[nx][ny]);
                            }
                        }
                    }
                }

            }
        }
    }
        public static void dfs2(int x,int y,int maxx,int maxy,Integer[][] graph,Corrd[][] corrds){
            Stack<Corrd> st = new Stack<Corrd>();
            if(graph[x][y]=='#'){
                return;
            }
            st.push(corrds[x][y]);
            corrds[x][y].color++;
            while(!st.empty()){
                Corrd p = st.pop();
              //  System.out.println(p.x+" "+p.y);
                for(int i=0;i<4;i++){
                    int nx = p.x+dirr[i][0];
                    int ny = p.y+dirr[i][1];
                    if(nx>=0 && nx<maxx && ny>=0 && ny<maxy && corrds[nx][ny].color==1){
                        if(!(graph[nx][ny]=='#')){
                            corrds[nx][ny].color++;
                            st.push(corrds[nx][ny]);
                        }
                    }

                }
            }

    }


    public static class Corrd{
        int x;
        int y;
        int color;
        Corrd(int x,int y){
            this.x = x;
            this.y = y;
            this.color =0;
        }
    }
}