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 codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Solution
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner scan=new Scanner(System.in);
		int t=scan.nextInt();
		for(int p=0;p<t;p++){
		    int n=scan.nextInt();
		    int k=scan.nextInt();
		    int[] a=new int[n];
		    for(int i=0;i<n;i++){
		        a[i]=scan.nextInt();
		    }
		    HashMap<Integer,Integer> map=new HashMap<>();
		    for(int i=0;i<n/2;i++){
		        int sum=a[i]+a[n-1-i];
		        if(map.containsKey(sum)){
		            map.put(sum,map.get(sum)+1);
		        }else{
		            map.put(sum,1);
		        }
		    }
		    int[] min=new int[n/2];
		    int[] max=new int[n/2];
		    for(int i=0;i<n/2;i++){
		        if(a[i]>a[n-i-1]){
		            min[i]=1+a[n-i-1];
		            max[i]=a[i]+k;
		        }else{
		            min[i]=1+a[i];
		            max[i]=a[n-i-1]+k;
		        }
		    }
		  //  for(int i=0;i<min.length;i++){
		  //      System.out.println(min[i]);
		  //  }
		  //  for(int i=0;i<max.length;i++){
		  //      System.out.println(max[i]);
		  //  }
		    Arrays.sort(max);
		    Arrays.sort(min);
		    int m=Integer.MAX_VALUE;
		    for(int i=2;i<=k;i++){
		        int temp=getPosMax(min,i);
		      //  System.out.println(temp+" "+i);
		        int ans=temp+2*(n/2-temp);
		        if(map.containsKey(i)){
		            ans-=map.get(i);
		        }
		        m=Math.min(ans,m);
		    }
		    for(int i=k+1;i<=2*k;i++){
		        int temp=getPosMin(max,i);
		      //  System.out.println(temp+" "+i);
		        int ans=2*temp+(n/2-temp);
		        if(map.containsKey(i)){
		            ans-=map.get(i);
		        }
		        m=Math.min(ans,m);
		    }
		    System.out.println(m);
		}
		
	}
	static int getPosMin(int[] a,int key){
	    int s=0,e=a.length-1;
	    while(s<=e){
	        int mid=(s+e)/2;
	        if(a[mid]<key&&(mid+1>=a.length||a[mid+1]>=key)){
	            return mid+1;
	        }
	        if((mid-1<s&&a[mid]>=key)){
	            return mid;
	        }
	        else if(a[mid]<key){
	            s=mid+1;
	        }else{
	            e=mid-1;
	        }
	    }
	    return -1;
	}
	static int getPosMax(int[] a,int key){
	    int s=0,e=a.length-1;
	    while(s<=e){
	        int mid=(s+e)/2;
	        if(a[mid]<=key&&(mid+1>=a.length||a[mid+1]>key)){
	            return mid+1;
	        }
	        if((mid-1<s&&a[mid]>key)){
	            return mid;
	        }
	        else if(a[mid]<=key){
	            s=mid+1;
	        }else{
	            e=mid-1;
	        }
	    }
	    return -1;
	}
	static int findMax(int min[],int max[],int n)     
    {    
        Arrays.sort(min); 
        Arrays.sort(max); 
      
        int in = 1, max_num = 1, temp = min[0]; 
        int i = 1, j = 0; 
      
        while (i < n && j < n) 
        { 
            if (min[i] <= max[j]) 
            { 
                in++; 
      
                if (in > max_num) 
                { 
                    max_num = in; 
                    temp = min[i]; 
                } 
                i++; 
            } 
            else 
            {  
                in--; 
                j++; 
            } 
        }
        return max_num;
    }
}