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.math.BigInteger;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        new Main().run();}


    long get(int p, int b){
        long s = 0;
        long f = 1;
        while(p!=0){
            s += f*(p%10);
            if(p%10>=b){
                return -10000;
            }
            p /= 10;
            f *= b;
        }
        return s;
    }


    long get(int num){
        if(num==1){
            return 0;
        }
        long s = 1;
        for(int i=2;i*i<=num;++i){
            if(num%i==0){
                s += i;
                if(num/i!=i){
                    s += num/i;
                }
            }
        }

        return s;
    }


    long inv(long a, long MOD) {
        //return fpow(a, MOD-2, MOD);
        return a==1?1:(long )(MOD-MOD/a)*inv(MOD%a, MOD)%MOD;
    }

    // 计算某个特别大的组合数
    long C(long n,long m, long MOD) {
        if(m+m>n)m=n-m;
        long up=1,down=1;
        for(long i=0;i<m;i++)
        {
            up=up*(n-i);
            down=down*(i+1);
        }
        return up/down;
    }

    boolean ok(String s){
        for(int i=0;i<s.length()/2;++i){
            if(s.charAt(i)!=s.charAt(s.length()-1-i)){
                return false;
            }
        }
        return true;
    }

    int fact[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
    int[] revContor(int bits, int rank) {
        rank--; //有 rank - 1 个排列比目标序列要小
        boolean vis[] = new boolean[bits+1];
        int res[] = new int[bits];

        int n, residue = rank;
        for (int i = 0; i < bits; ++i) {
            n = residue / (fact[bits - i - 1]);
            residue = residue % (fact[bits - i - 1]);

            for (int j = 1; j <= bits; ++j) {
                if (!vis[j] && n--==0) {
                    vis[j] = true;
                    res[i] = j-1;
                    break;
                }
            }
        }
        return res;
    }

    static long mul(long a, long b, long p)
    {
        long res=0,base=a;
        while(b>0)
        {
            if((b&1L)>0)
                res=(res+base)%p;
            base=(base+base)%p;
            b>>=1;
        }
        return res;
    }

    static long mod_pow(long k,long n,long p){
        long res = 1L;
        long temp = k%p;
        while(n!=0L){
            if((n&1L)==1L){
                res = mul(res,temp,p);
            }
            temp = mul(temp,temp,p);
            n = n>>1L;
        }
        return res%p;
    }



    boolean ok(Vector v1,Vector v2){

        boolean r = Math.min(v1.from.x,v1.end.x) <= Math.max(v2.from.x,v2.end.x) &&
                Math.min(v2.from.x,v2.end.x) <= Math.max(v1.from.x,v1.end.x) &&
                Math.min(v1.from.y,v1.end.y) <= Math.max(v2.from.y,v2.end.y) &&
                Math.min(v2.from.y,v2.end.y) <= Math.max(v1.from.y,v1.end.y);
        if(!r) return false;

        long c1 = cross(new Vector(v2.from, v1.end), v2);
        long c2 = cross(new Vector(v2.from, v1.from), v2);
        if(c1>0&&c2>0||c1<0&&c2<0) return false;

        c1 = cross(new Vector(v1.from, v2.end), v1);
        c2 = cross(new Vector(v1.from, v2.from), v1);
        if(c1>0&&c2>0||c1<0&&c2<0) return false;

        return true;
    }




    void solve() {

//        int mp[][] = new int[25][25];
//        int ct = 0;
//        while(true){
//            int x = ni();
//            int y = ni();
//            if(x==0&&y==0) break;
//            mp[x][y] = 1;
//            ct++;
//        }
//        int time = 0;
//
//        while(true){
//            int f1 = 1;
//            int f2 = 1;
//            int col = 0;
//            int lst = -1;
//            for(int i=f2+1;i<=24;++i){
//                if(mp[f1][i]==1){
//                    col++;
//                    lst = i;
//                }
//            }
//            if(col>0){
//                for(int i=f2+1;i<=24;++i){
//                    if(mp[f1][i]==1){
//                        mp[f1][i] = 0;
//                    }
//                }
//                f1 = lst;
//                ct -= col;
//                continue;
//            }else{
//                if(f1+1<=24){
//                    f1++;
//                    if(mp[f1][f2]==1){
//                        mp[f1][f2] = 0;
//                        col++;
//                    }
//                }else{
//                    f1 = 24;
//                    f2 = 24;
//                }
//            }
//        }

        ot:for(int i=ni();i>=1;--i){
            int n = ni();
            int k = ni();
            int a[] = na(n);
            int cg = n;
            int ct[] = new int[2*k+2];

                for(int j=0,l=n-1;j<n/2;j++,--l){
                    int s = a[j]+a[l];
                    int lg = Math.max(a[j],a[l]);
                    int sm = Math.min(a[j],a[l]);
                    ct[2]+=2;
                    ct[sm+1] -= 2;
                    ct[sm+1]++;
                    ct[s]--;
                    ct[s+1]++;
                    ct[lg+k+1]--;
                    ct[lg+k+1]+=2;
                }
                int sum = 0;
                int r = n;
                for(int j=2;j<=2*k;++j){
                    sum += ct[j];
                    r =Math.min(r,sum);
                }
                println(r);

        }


    }


    boolean same(long a,long b){
        return a>=0&&b>=0||a<=0&&b<=0;
    }


   boolean vis[][] = new boolean[21][21];

    void go(int full[],int[] v){

        if(vis[v[1]][v[2]]){
            return;
        }else{
            vis[v[1]][v[2]] = true;
        }

        for(int i=0;i<3;++i){
            if(v[i]>0){
                for(int j=0;j<3;++j){
                    if(v[j]<full[j]){
                        int amt = Math.min(full[j]-v[j],v[i]);
                        v[i] -= amt;
                        v[j] += amt;

                        go(full,v);

                        v[i] += amt;
                        v[j] -= amt;
                    }

                }
            }
        }


    }

    double cross(double x1,double y1,double x2,double y2){
        return x1*y2-y1*x2;
    }


    long Josephus(long N,long  K) {
        if (N == 1L) return 0L;
        if(N < K) {
            long ret = 0;
            for (long i = 2; i <= N; ++i)
                ret = (ret + K) % i;

            return ret;
        }
        long ret = Josephus(N - N / K, K);
        if(ret < N % K) {
            ret = ret - (N % K) + N;
        }else {
            ret = ret - (N % K) +(ret - (N % K)) /(K - 1L);
        }
        return ret;
    }

    static int groups = 0;
    static int[] fa;
    static int[] sz;

    static void init(int n) {
        groups = n;
        fa = new int[n];
        for (int i = 1; i < n; ++i) {
            fa[i] = i;
        }
        sz = new int[n];
        Arrays.fill(sz, 1);
    }

    static int root(int p) {
        while (p != fa[p]) {
            fa[p] = fa[fa[p]];
            p = fa[p];
        }
        return p;
    }

    static void combine(int p, int q) {
        int i = root(p);
        int j = root(q);
        if (i == j) {
            return;
        }
        if (sz[i] < sz[j]) {
            fa[i] = j;
            sz[j] += sz[i];
        } else {
            fa[j] = i;
            sz[i] += sz[j];
        }
        groups--;
    }

    class Point {
        long x;
        long y;

        Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    class Vector {
        Point from;
        Point end;

        Vector(Point from, Point end){
            this.from = from;
            this.end = end;
        }
    }

    public long cross(Vector v1, Vector v2){
        return (v1.end.x - v1.from.x)*(v2.end.y - v2.from.y) - (v2.end.x - v2.from.x)*(v1.end.y - v1.from.y);
    }

    long gcd(long a,long b){ return b==0?a: gcd(b,a%b);}
    int gcd(int a,int b){ return b==0?a: gcd(b,a%b);}
    InputStream is;PrintWriter out;
    void run() throws Exception {is = System.in;
        //   is  = new FileInputStream("C:\\Users\\Luqi\\Downloads\\P3119_6.in");
        out = new PrintWriter(System.out);solve();out.flush();}
    private byte[] inbuf = new byte[2];
    public int lenbuf = 0, ptrbuf = 0;
    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {lenbuf = is.read(inbuf);} catch (IOException e) {throw new InputMismatchException();}
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];}
    private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}
    private int skip() {int b;while((b = readByte()) != -1 && isSpaceChar(b));return b;}
    private double nd() {return Double.parseDouble(ns());}
    private char nc() {return (char) skip();}
    private char ncc() {int b;while((b = readByte()) != -1 && !(b >= 32 && b <= 126));return (char)b;}
    private String ns() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[] ns(int n) {char[] buf = new char[n];int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) { buf[p++] = (char) b;b = readByte(); }
        return n == p ? buf : Arrays.copyOf(buf, p);}
    private String nline() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') { sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[][] nm(int n, int m) {char[][] a = new char[n][];for (int i = 0; i < n; i++) a[i] = ns(m);return a;}
    private int[] na(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = ni();return a;}
    private long[] nal(int n) { long[] a = new long[n];for (int i = 0; i < n; i++) a[i] = nl();return a;}
    private int ni() { int num = 0, b; boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    private long nl() { long num = 0; int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9')  num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    void print(Object obj){out.print(obj);}
    void println(Object obj){out.println(obj);}
    void println(){out.println();}
    void printf(String f,Object ... args){out.printf(f, args);}
}