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:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
300IQ as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class F
   {
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int T = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         while(T-->0)
         {
            int N = Integer.parseInt(infile.readLine());
            int[] arr = new int[N];
            st = new StringTokenizer(infile.readLine());
            for(int i=0; i < N; i++)
               arr[i] = Integer.parseInt(st.nextToken());
            int inversions = invcnt(arr);
            if(distinct(arr) && inversions%2 == 1)
               sb.append("-1\n");
            else
            {
               if(inversions%2 == 1)
               {
                  int a = -1; int b = -1;
                  int doubled = -1;
                  matcha:for(int i=0; i < N; i++)
                     for(int j=i+1; j < N; j++)
                        if(arr[i] == arr[j])
                        {
                           a = i;
                           b = j;
                           doubled = arr[i];
                           break matcha;
                        }
                  //permutation
                  ArrayList<Thing> temp = new ArrayList<Thing>();
                  for(int i=0; i < N; i++)
                     temp.add(new Thing(i, arr[i]));
                  Collections.sort(temp);
                  int boof = 0;
                  for(Thing t: temp)
                     arr[t.dex] = boof++;
                  int t = arr[a];
                  arr[a] = arr[b];
                  arr[b] = t;
               }
               else
               {
                  //normal compression
                  ArrayList<Thing> temp = new ArrayList<Thing>();
                  for(int i=0; i < N; i++)
                     temp.add(new Thing(i, arr[i]));
                  Collections.sort(temp);
                  int boof = 0;
                  for(Thing t: temp)
                     arr[t.dex] = boof++;
               }
               //swaps
               ArrayList<Integer> moves = new ArrayList<Integer>();
               for(int curr=0; curr < N; curr++)
               {
                  int loc = -1;
                  for(int i=0; i < N; i++)
                     if(arr[i] == curr)
                     {
                        loc = i;
                        break;
                     }
                  while(loc > curr)
                  {
                     if(loc-1 == curr)
                     {
                        moves.add(curr);  moves.add(curr);
                        shift(arr, curr); shift(arr, curr);
                        loc--;
                     }
                     else
                     {
                        moves.add(loc-2);
                        shift(arr, loc-2);
                        loc -= 2;
                     }
                  }
               }
               sb.append(moves.size()+"\n");
               for(int x: moves)
                  sb.append(x+1).append(" ");
               sb.append("\n");
            }
         }
         System.out.print(sb);
      }
      public static void shift(int[] arr, int dex)
      {
         int a = arr[dex];
         int b = arr[dex+1];
         int c = arr[dex+2];
         arr[dex] = c;
         arr[dex+1] = a;
         arr[dex+2] = b;
      }
      public static int invcnt(int[] arr)
      {
         int res = 0;
         for(int a=0; a < arr.length; a++)
            for(int b=a+1; b < arr.length; b++)
               if(arr[a] > arr[b])
                  res++;
         return res;
      }
      public static boolean distinct(int[] arr)
      {
         HashSet<Integer> set = new HashSet<Integer>();
         for(int x: arr)
            if(!set.add(x))
               return false;
         return true;
      }
   }
   class Thing implements Comparable<Thing>
   {
      public int val;
      public int dex;
      
      public Thing(int a, int b)
      {
         dex = a;
         val = b;
      }
      public int compareTo(Thing oth)
      {
         if(val == oth.val)
            return dex-oth.dex;
         return val-oth.val;
      }
   }