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.*;
import java.util.*;
import java.math.*;

public class F {
    static final boolean RUN_TIMING = false;
    static char[] inputBuffer = new char[1 << 20];
    static PushbackReader in = new PushbackReader(new BufferedReader(new InputStreamReader(System.in)), 1 << 20);
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public void go() throws IOException {
        // in = new PushbackReader(new BufferedReader(new FileReader(new File("test.txt"))), 1 << 20);
        // out = new PrintWriter(new FileWriter(new File("output.txt")));
        int zzz = ipar();
        for (int zz = 0; zz < zzz; zz++) {
            int n = ipar();
            int[] arr = iapar(n);
            int[][] sorted = new int[n][2];
            ArrayList<int[]> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(new int[] {arr[i], i});
            }
            Collections.sort(list, (a, b) -> a[0] - b[0]);
            for (int i = 0; i < n; i++) {
                sorted[i] = list.get(i);
            }
            int[] p = new int[n];
            for (int i = 0; i < n; i++) {
                p[sorted[i][1]] = i;
            }
            int invCount = 0;
            for (int i = 0; i < n; i++) {
                for (int e = i+1; e < n; e++) {
                    if (p[i] > p[e]) {
                        invCount++;
                    }
                }
            }
            if (invCount % 2 == 1) {
                boolean foundSwap = false;
                OUTER:
                for (int i = 0; i < n; i++) {
                    for (int e = i+1; e < n; e++) {
                        if ((p[i] + p[e]) % 2 == 1 && arr[i] == arr[e]) {
                            int temp = p[i];
                            p[i] = p[e];
                            p[e] = temp;
                            foundSwap = true;
                            break OUTER;
                        }
                    }
                }
                if (!foundSwap) {
                    out.println(-1);
                    continue;
                }
            }
            ArrayList<Integer> ops = new ArrayList<>();
            for (int i = 0; i < n-2; i++) {
                int s = 0;
                for (int e = i; e < n; e++) {
                    if (p[e] == i) {
                        s = e;
                        break;
                    }
                }
                while (s >= i+2) {
                    ops.add(s-2);
                    int temp = arr[s];
                    arr[s] = arr[s-1];
                    arr[s-1] = arr[s-2];
                    arr[s-2] = temp;
                    temp = p[s];
                    p[s] = p[s-1];
                    p[s-1] = p[s-2];
                    p[s-2] = temp;
                    s -= 2;
                }
                if (s == i+1) {
                    ops.add(s-1);
                    ops.add(s-1);
                    int temp = arr[s-1];
                    arr[s-1] = arr[s];
                    arr[s] = arr[s+1];
                    arr[s+1] = temp;
                    temp = p[s-1];
                    p[s-1] = p[s];
                    p[s] = p[s+1];
                    p[s+1] = temp;
                }
            }
            out.println(ops.size());
            for (int i = 0; i < ops.size(); i++) {
                out.print(ops.get(i)+1);
                out.print(" ");
            }
            out.println();
        }
    }

    public int ipar() throws IOException {
        return Integer.parseInt(spar());
    }

    public int[] iapar(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar() throws IOException {
        return Long.parseLong(spar());
    }

    public long[] lapar(int n) throws IOException {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar() throws IOException {
        return Double.parseDouble(spar());
    }

    public String spar() throws IOException {
        int len = 0;
        int c;
        do {
            c = in.read();
        } while (Character.isWhitespace(c) && c != -1);
        if (c == -1) {
            throw new NoSuchElementException("Reached EOF");
        }
        do {
            inputBuffer[len] = (char)c;
            len++;
            c = in.read();
        } while (!Character.isWhitespace(c) && c != -1);
        while (c != '\n' && Character.isWhitespace(c) && c != -1) {
            c = in.read();
        }
        if (c != -1 && c != '\n') {
            in.unread(c);
        }
        return new String(inputBuffer, 0, len);
    }

    public String linepar() throws IOException {
        int len = 0;
        int c;
        while ((c = in.read()) != '\n' && c != -1) {
            if (c == '\r') {
                continue;
            }
            inputBuffer[len] = (char)c;
            len++;
        }
        return new String(inputBuffer, 0, len);
    }

    public boolean haspar() throws IOException {
        String line = linepar();
        if (line.isEmpty()) {
            return false;
        }
        in.unread('\n');
        in.unread(line.toCharArray());
        return true;
    }

    public static void main(String[] args) throws IOException {
        long time = 0;
        time -= System.nanoTime();
        new F().go();
        time += System.nanoTime();
        if (RUN_TIMING) {
            System.out.printf("%.3f ms%n", time / 1000000.0);
        }
        out.flush();
        in.close();
    }
}