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