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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int main() {
  int t, ad = 0;
  cin >> t;
  while (t--) {
    ad++;
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    int mn = n;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    vector<int> steps;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n - 2; j++) {
        if (a[j] <= a[j + 1] and a[j + 1] <= a[j + 2]) continue;
        if (max(a[j], a[j + 1]) >= a[j + 2]) {
          swap(a[j], a[j + 1]);
          swap(a[j], a[j + 2]);
          steps.push_back(j);
        }
        if (a[j] <= a[j + 1] and a[j + 1] <= a[j + 2]) continue;
        if (max(a[j], a[j + 1]) >= a[j + 2]) {
          swap(a[j], a[j + 1]);
          swap(a[j], a[j + 2]);
          steps.push_back(j);
        }
      }
    }
    int r = -1;
    for (int i = 0; i < n - 1; i++) {
      if (a[i] == a[i + 1]) {
        r = i;
        break;
      }
    }
    if (a[0] > a[1] and r > 0) {
      vector<int> res, res1;
      for (int i = r; i > 2; i--) {
        res.push_back(i - 1);
        res.push_back(i - 1);
        res1.push_back(i - 1);
      }
      reverse(res1.begin(), res1.end());
      for (auto it : res) {
        int j = it;
        swap(a[j], a[j + 1]);
        swap(a[j], a[j + 2]);
        steps.push_back(it);
      }
      steps.push_back(1);
      steps.push_back(0);
      int j = 1;
      swap(a[j], a[j + 1]);
      swap(a[j], a[j + 2]);
      j = 0;
      swap(a[j], a[j + 1]);
      swap(a[j], a[j + 2]);
      for (auto it : res1) {
        int j = it;
        swap(a[j], a[j + 1]);
        swap(a[j], a[j + 2]);
        steps.push_back(it);
      }
    }
    bool fl = true;
    for (int i = 0; i < n - 1; i++) {
      if (a[i] > a[i + 1]) {
        fl = false;
      }
    }
    if (fl == false and r < 0) {
      cout << "-1\n";
    } else {
      cout << steps.size() << endl;
      for (auto it : steps) {
        cout << it + 1 << " ";
      }
      cout << endl;
    }
  }
}