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:
/**
 * BaZ :D
 */

import java.text.DecimalFormat;
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class ACMIND
{
    static FastReader scan;
    static PrintWriter pw;
    static long MOD = 1_000_000_007;
    static long INF = 2_000_000_000_000_000_000L;
    static long inf = 2_000_000_000;
    public static void main(String[] args) {
        new Thread(null,null,"BaZ",1<<27)
        {
            public void run()
            {
                try
                {
                    solve();
                }
                catch(Exception e)
                {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }

    static int n,k,arr[],BIT[];
    static void solve() throws IOException {
        scan = new FastReader();
        pw = new PrintWriter(System.out, true);
        StringBuilder sb = new StringBuilder();
        int t = ni();
        while (t-->0) {
            n = ni();
            k = ni();
            arr = new int[n];
            for(int i=0;i<n;++i) {
                arr[i] = ni();
            }
            BIT = new int[2*k+1];
            ArrayList<Pair> list = new ArrayList<>();
            for(int i=0;i<n/2;++i) {
                list.add(new Pair(arr[i], arr[n-1-i]));
            }
            Collections.sort(list);
            int less[] = new int[2*k+2];
            int greater[] = new int[2*k+2];
            for(int i=0;i<n/2;++i) {
                int sum = arr[i]+arr[n-1-i];
                less[sum+1]++;
                greater[sum-1]++;
            }
            for(int i=1;i<=2*k+1;++i) {
                less[i]+=less[i-1];
            }
            for(int i=2*k;i>=0;--i) {
                greater[i]+=greater[i+1];
            }
//            pa("less", less);
//            pa("greater", greater);
//            pa("list", list);
            int ans = n;
            BIT = new int[2*k+1];
            int ptr = list.size();
            for(int x=k;x>=2;--x) {
                while (ptr-1>=0 && list.get(ptr-1).x + list.get(ptr-1).y > x) {
                    ptr--;
                    update(list.get(ptr).x, 1);
                }
                int total_greater = query(2*k);
                int valid = query(x-1);
                int ispe = valid + 2*(total_greater - valid) + less[x];
                //pl("x : "+x+" total_greater : "+total_greater+" valid :  "+valid+"  ispe : "+ispe);
                ans = min(ispe, ans);
            }

            BIT = new int[2*k+1];
            ptr = -1;
            for(int x=k+1;x<=2*k;++x) {
                while (ptr+1 < list.size() && list.get(ptr+1).x + list.get(ptr+1).y < x) {
                    ptr++;
                    update(list.get(ptr).y, 1);
                }
                int total_less = query(2*k);
                int valid = total_less - query(x-k-1);
                int ispe = valid + 2*(total_less - valid) + greater[x];
                //pl("x : "+x+" total_less : "+total_less+" valid :  "+valid+"  ispe : "+ispe);
                ans = min(ans, ispe);
            }
            pl(ans);
        }
        pw.flush();
        pw.close();
    }

    static class Pair implements Comparable<Pair>
    {
        int x,y;
        Pair(int x,int y)
        {
            this.x=min(x,y);
            this.y=max(x,y);
        }
        public int compareTo(Pair other)
        {
            return (this.x+this.y) - (other.x+other.y);
        }
        public String toString()
        {
            return "("+x+","+y+")";
        }
    }
    static void update(int index,int val)
    {
        for(int i=index;i<=2*k;i+=i&-i)
            BIT[i]+=val;
    }
    static int query(int index)
    {
        int sum = 0;
        for(int i=index;i>0;i-=i&-i)
            sum+=BIT[i];
        return sum;
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[1000000];
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }
}