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.IOException;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
//    public static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
//
//    public static long nextInt() {
//        try {
//            in.nextToken();
//        } catch (IOException e) {
//            // TODO Auto-generated catch block
//            e.printStackTrace();
//        }
//        return (long) in.nval;
//    }
//
//    public static String next() {
//        try {
//            in.nextToken();
//        } catch (IOException e) {
//            // TODO Auto-generated catch block
//            e.printStackTrace();
//        }
//        return in.sval;
//    }
    static int a[];

    static int cnt;

    static ArrayList<Integer> ls;

    static void f(int i) {
        cnt++;
        ls.add(i + 1);
        int x = a[i], y = a[i + 1], z = a[i + 2];
        a[i] = z;
        a[i + 1] = x;
        a[i + 2] = y;
    }

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            cnt = 0;
            ls = new ArrayList<Integer>();
            int n = in.nextInt();
            a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = in.nextInt();
            for (int i = 0; i < n - 2; i++) {
                int min = a[i], mini = i;
                for (int j = i + 1; j < n; j++) {
                    if (min > a[j]) {
                        min = a[j];
                        mini = j;
                    }
                }
                while (mini >= i + 2) {
                    mini -= 2;
                    f(mini);
                }
                if (mini == i + 1) {
                    f(i);
                    f(i);
                }
            }
            if (a[n - 1] < a[n - 2]) {
                if (a[n - 3] == a[n - 1])
                    f(n - 3);
                else
                    for (int i = n - 4; i >= 0; i--) {
                        if (a[i] == a[i + 1]) {
                            for (int j = i; j < n - 2; j++) {
                                f(j);
                                f(j);
                            }
                            break;
                        }
                    }
            }
            if (a[n - 1] < a[n - 2] || cnt > n * n)
                out.println(-1);
            else {
                out.println(cnt);
                for (int i : ls)
                    out.print(i + " ");
                out.println();
            }

        }
        out.flush();
    }
}