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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FCyclicShiftsSorting solver = new FCyclicShiftsSorting();
        solver.solve(1, in, out);
        out.close();
    }

    static class FCyclicShiftsSorting {
        boolean inv;
        int[] invIndex = new int[2];

        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int t = in.nextInt();
            while (t-- > 0) {
                int n = in.nextInt();
                int[] a = new int[n];
                in.readArr(a);
                inv = false;
                int num = getInvNum(a);
                if (num == 0) {
                    out.println(0);
                    out.println();
                    continue;
                }
//            if (num%2==1 && !inv) {
//                out.println(-1);
//                continue;
//            }
                if (num % 2 == 1 && inv) {
                    int tmp = a[invIndex[0]];
                    a[invIndex[0]] = a[invIndex[1]];
                    a[invIndex[1]] = tmp;
                }

                List<Integer> ans = calAns(a);
                if (ans == null) {
                    out.println(-1);
                    continue;
                }
                out.println(ans.size());
                for (int i = 0; i < ans.size(); i++) {
                    out.print(ans.get(i) + " ");
                }
                out.println();

            }
        }

        private List<Integer> calAns(int[] a) {
            List<Integer> ans = new ArrayList<>();
            int len = a.length;
            for (int i = 0; i < len - 2; i++) {
                int min = Integer.MAX_VALUE;
                int index = -1;
                for (int j = i; j < len; j++) {
                    if (a[j] < min) {
                        min = a[j];
                        index = j;
                    }
                }
                while (index - 2 >= i) {
                    ans.add(index - 1);
                    move(index - 2, a);
                    index -= 2;
                }
                if (index > i) {
                    if (index >= len - 1) {
                        return null;
                    }
                    move(index - 1, a);
                    move(index - 1, a);
                    ans.add(index);
                    ans.add(index);
                }
            }
            if (!isSort(a)) {
                for (int i = 0; i < 3; i++) {
                    if (isSort(a)) break;
                    move(len - 3, a);
                    ans.add(len - 2);
                }
            }
            if (!isSort(a)) return null;

            return ans;
        }

        private boolean isSort(int[] a) {
            for (int i = 0; i < a.length - 1; i++) {
                if (a[i] > a[i + 1]) return false;
            }
            return true;
        }

        private void move(int index, int[] a) {
            int tmp2 = a[index + 2];
            int tmp1 = a[index + 1];
            a[index + 2] = tmp1;
            a[index + 1] = a[index];
            a[index] = tmp2;
        }

        private int getInvNum(int[] a) {
            int len = a.length;
            int[] flag = new int[502];

            int index = -1;
            for (int i = 0; i < len; i++) {
                int tmp = a[i];
                a[i] = a[i] * 500 + flag[a[i]];
                flag[tmp]++;
                if (flag[tmp] > 1) {
                    index = i;
                }
            }

            int l = -1;
            int r = -1;
            if (index != -1) {
                for (int i = len - 1; i >= 0; i--) {
                    if (a[i] / 500 == a[index] / 500) {
                        if (r == -1) {
                            r = i;
                        } else if (l == -1) {
                            l = i;
                        }
                    }
                }
                inv = true;
                invIndex[0] = l;
                invIndex[1] = r;
            }


            int num = 0;
            for (int i = 0; i < len - 1; i++) {
                for (int j = i + 1; j < len; j++) {
                    if (a[i] > a[j]) {
                        num++;
                    }
                }
            }
            return num;
        }

    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            while (st == null || (!st.hasMoreElements())) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }

            }
            return st.nextToken();
        }

        public void readArr(int[] a) {
            for (int i = 0; i < a.length; i++) {
                a[i] = nextInt();
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}