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:
//package codeforces;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.*;
import java.util.ArrayList;
public final class Codeforces {
    static ArrayList<Long>factors;
    static int p=1000000007;
    public static void main(String[] args) throws Exception{
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);        
        FastReader sc = new FastReader();
        int tc=sc.nextInt(),n,a[],k,pre[],ans,cnt0,cnt1,cnt2;
        HashMap<Integer,Integer>map;
        while(tc-->0)
        {
          n=sc.nextInt();
          k=sc.nextInt();
          a=new int[n];
          map=new HashMap<>();
          pre=new int[2*k+1];
          ans=Integer.MAX_VALUE;
          for(int i=0;i<n;i++)a[i]=sc.nextInt();
          for(int i=0;i<n/2;i++)
          {
             if(!map.containsKey(a[i]+a[n-1-i])) map.put(a[i]+a[n-1-i],1);
             else map.put(a[i]+a[n-i-1], map.get(a[i]+a[n-i-1])+1);
             pre[Math.min(a[i],a[n-i-1])+1]++;
             if(Math.max(a[i],a[n-i-1])+ k+1<=2*k)pre[Math.max(a[i],a[n-i-1])+ k+1]--;
          }
          
          
          for(int i=1;i<=2*k;i++)pre[i]+=pre[i-1];
          
          
          for(int i=2;i<=2*k;i++)
          {
              cnt0=map.containsKey(i)?map.get(i):0;
              cnt1=pre[i]-cnt0;
              cnt2=n/2-cnt1-cnt0;
              ans=Math.min(ans, 2*cnt2+cnt1);
             // System.out.println(" cnt0 cnt1 cnt2 "+cnt0+" "+cnt1+" "+cnt2+" ans "+ans+" i is "+i);
          }
          out.write(ans+"\n");
      
         }
           out.flush();

        }

    


public static class boolarray {
  int array[];

  public boolarray( int b[] ) {
     array = b;
  }

  public int hashCode() {
    int hash = 0;
        for(int v:array)
          hash += (int)pow(v,3);
    return hash;
  }
  
  public static long pow(int x,int n)
  {
      if(n==0)return 1;
      long temp=pow(x,n/2);
      if(n%2==1)return ((x%p*temp%p)%p*temp%p)%p;
      else return (temp%p*temp%p)%p;
  }

  public boolean equals( Object b ) {
     if (!(b instanceof boolarray))
        return false;
     if ( array.length != ((boolarray)b).array.length )
        return false;
     for (int i = 0; i < array.length; i++ )
        if (array[i] != ((boolarray)b).array[i])
           return false;
     return true;
  }
}

   
    static class FastReader {        

        BufferedReader br;        
        StringTokenizer st;        
       
        public FastReader() {            
            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 nextInt() {            
            return Integer.parseInt(next());            
        }        
        
        long nextLong() {            
            return Long.parseLong(next());            
        }        
        
        double nextDouble() {            
            return Double.parseDouble(next());            
        }        
        
        String nextLine() {            
            String str = "";            
            try {                
                str = br.readLine();                
            } catch (IOException e) {                
                e.printStackTrace();                
            }            
            return str;            
        }        
    }   
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////// 
}