Problem: You are given an array a consisting of n integers.

In one move, you can choose some index i (1 ≤ i ≤ n - 2) and shift the segment [a_i, a_{i + 1}, a_{i + 2}] cyclically to the right (i.e. replace the segment [a_i, a_{i + 1}, a_{i + 2}] with [a_{i + 2}, a_i, a_{i + 1}]). 

Your task is to sort the initial array by no more than n^2 such operations or say that it is impossible to do that.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (3 ≤ n ≤ 500) — the length of a. The second line of the test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 500), where a_i is the i-th element a.

It is guaranteed that the sum of n does not exceed 500.

Output

For each test case, print the answer: -1 on the only line if it is impossible to sort the given array using operations described in the problem statement, or the number of operations ans on the first line and ans integers idx_1, idx_2, ..., idx_{ans} (1 ≤ idx_i ≤ n - 2), where idx_i is the index of left border of the segment for the i-th operation. You should print indices in order of performing operations.

Example

Input


5
5
1 2 3 4 5
5
5 4 3 2 1
8
8 4 5 2 3 6 7 3
7
5 2 1 6 4 7 3
6
1 2 3 3 6 4


Output


0

6
3 1 3 2 2 3 
13
2 1 1 6 4 2 4 3 3 4 4 6 6 
-1
4
3 3 4 4 

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());
        }

    }
}