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

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T>
using mat = vector<vector<T>>;
template <int mod>
struct modint {
  int x;
  modint() : x(0) {}
  modint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  modint &operator+=(const modint &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  modint &operator-=(const modint &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  modint &operator*=(const modint &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  modint &operator/=(const modint &p) {
    *this *= p.inverse();
    return *this;
  }
  modint operator-() const { return modint(-x); }
  modint operator+(const modint &p) const { return modint(*this) += p; }
  modint operator-(const modint &p) const { return modint(*this) -= p; }
  modint operator*(const modint &p) const { return modint(*this) *= p; }
  modint operator/(const modint &p) const { return modint(*this) /= p; }
  bool operator==(const modint &p) const { return x == p.x; }
  bool operator!=(const modint &p) const { return x != p.x; }
  modint inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return modint(u);
  }
  modint pow(int64_t n) const {
    modint ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const modint &p) { return os << p.x; }
  friend istream &operator>>(istream &is, modint &a) {
    int64_t t;
    is >> t;
    a = modint<mod>(t);
    return (is);
  }
  static int get_mod() { return mod; }
};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
T mypow(T x, ll n) {
  T ret = 1;
  while (n > 0) {
    if (n & 1) (ret *= x);
    (x *= x);
    n >>= 1;
  }
  return ret;
}
ll modpow(ll x, ll n, const ll mod) {
  ll ret = 1;
  while (n > 0) {
    if (n & 1) (ret *= x);
    (x *= x);
    n >>= 1;
    x %= mod;
    ret %= mod;
  }
  return ret;
}
uint64_t my_rand(void) {
  static uint64_t x = 88172645463325252ULL;
  x = x ^ (x << 13);
  x = x ^ (x >> 7);
  return x = x ^ (x << 17);
}
ll popcnt(ull x) { return __builtin_popcountll(x); }
template <typename T>
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  bool operator<(const edge<T> &r) const { return cost < r.cost; }
  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
struct Timer {
  clock_t start_time;
  void start() { start_time = clock(); }
  int lap() { return (clock() - start_time) * 1000 / CLOCKS_PER_SEC; }
};
const long double eps = 0.000001;
const long double PI = 3.141592653589793;
template <typename T>
struct BIT {
  vector<T> data;
  BIT(int sz) { data.assign(++sz, 0); }
  T sum(int k) {
    T ret = 0;
    for (; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }
  void add(int k, T x) {
    for (++k; k < data.size(); k += k & -k) data[k] += x;
  }
  int search(long long k) {
    ++k;
    int res = 0;
    int N = 1;
    while (N < (int)data.size()) N *= 2;
    for (int i = N / 2; i > 0; i /= 2) {
      if (res + i < (int)data.size() && data[res + i] < k) {
        k = k - data[res + i];
        res = res + i;
      }
    }
    return res;
  }
  void show() {
    for (ll i = (0), max_i = (((ll)(data).size()) - 1); i < max_i; i++)
      cout << sum(i + 1) - sum(i) << ' ';
    cout << '\n';
  }
};
ll inversion_number(vector<int> &x, int n) {
  BIT<int> bit(n);
  ll res = 0;
  for (int &y : x) {
    res += bit.sum(n - 1 - y);
    bit.add(n - 1 - y, 1);
  }
  return res;
}
void move(vector<int> &x, vector<int> &y, int i) {
  assert(x.size() - 2 > i);
  int a = x[i], b = x[i + 1], c = x[i + 2];
  swap(y[a], y[b]);
  swap(y[c], y[b]);
  swap(x[i + 2], x[i + 1]);
  swap(x[i], x[i + 1]);
}
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<pair<int, int>> inv(n);
  for (ll i = (0), max_i = (n); i < max_i; i++)
    cin >> a[i], inv[i] = make_pair(a[i], i);
  sort((inv).begin(), (inv).end());
  vector<int> id(n);
  for (ll i = (0), max_i = (n); i < max_i; i++) id[i] = inv[i].second;
  int num = inversion_number(id, n);
  if (num % 2 == 1) {
    bool flag = false;
    for (ll i = (0), max_i = (n - 1); i < max_i; i++) {
      if (inv[i].first == inv[i + 1].first) {
        swap(inv[i].second, inv[i + 1].second);
        swap(id[i], id[i + 1]);
        flag = true;
        break;
      }
    }
    if (not flag) {
      cout << -1 << '\n';
      return;
    }
  }
  vector<int> now(n), now_inv(n);
  iota((now).begin(), (now).end(), 0);
  iota((now_inv).begin(), (now_inv).end(), 0);
  vector<int> ans;
  for (ll i = (0), max_i = (n); i < max_i; i++) {
    int a = id[i];
    while (now_inv[a] != i) {
      if (now_inv[a] == n - 1) {
        ans.push_back(now_inv[a] - 1);
        move(now, now_inv, now_inv[a] - 2);
        continue;
      }
      int tmp = now_inv[a] - 1;
      ans.push_back(tmp + 1);
      ans.push_back(tmp + 1);
      move(now, now_inv, tmp);
      move(now, now_inv, tmp);
    }
  }
  cout << ans.size() << '\n';
  for (ll i = (0), max_i = (ans.size()); i < max_i; i++) cout << ans[i] << ' ';
  cout << '\n';
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << setprecision(20);
  int t;
  cin >> t;
  for (ll _ = (0), max_i = (t); _ < max_i; _++) {
    solve();
  }
}