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 optimise GCC(-O2)
using namespace std;
mt19937_64 rang(
    chrono::high_resolution_clock::now().time_since_epoch().count());
long long rng(long long lim) {
  uniform_int_distribution<long long> uid(0, lim - 1);
  return uid(rang);
}
long long INF = LLONG_MAX;
const long long M = 1000000007, M2 = 998244353, M3 = 2013265921;
long long powm(long long, long long, long long);
long long modI(long long, long long);
long long PrimRoot(long long p, long long x);
void fft(vector<long long>& a, long long n, bool invert, long long m,
         long long x);
void PolyMult(vector<long long>& a, vector<long long>& b, vector<long long>& v,
              long long m, long long x);
void solve() {
  long long n;
  cin >> n;
  long long a[n];
  for (long long i = 0; i < n; i++) cin >> a[i];
  vector<long long> ans;
  long long b[n];
  for (long long i = 0; i < n; i++) b[i] = a[i];
  sort(b, b + n);
  for (long long i = 0; i < n - 2; i++) {
    for (long long j = i; j < n; j++) {
      if (a[j] == b[i]) {
        while (j != i) {
          ans.push_back(j - 2);
          swap(a[j - 2], a[j - 1]);
          swap(a[j - 2], a[j]);
          j -= 2;
        }
        goto meow;
      }
      j++;
    }
    for (long long j = i + 1; j < n; j++) {
      if (a[j] == b[i]) {
        while (j != i + 1) {
          ans.push_back(j - 2);
          swap(a[j - 2], a[j - 1]);
          swap(a[j - 2], a[j]);
          j -= 2;
        }
        ans.push_back(i);
        ans.push_back(i);
        swap(a[i], a[i + 1]);
        swap(a[i + 2], a[i + 1]);
        goto meow;
      }
      j++;
    }
  meow:;
  }
  if (a[n - 1] != b[n - 1]) {
    map<long long, long long> ct;
    bool ALLMIGHT = 0;
    for (long long i = 0; i < n; i++) {
      ct[a[i]]++;
      if (ct[a[i]] == 2) ALLMIGHT = 1;
    }
    if (ALLMIGHT == 0) {
      cout << -1 << endl;
      return;
    }
    long long curram_mf = n - 3;
    while (ALLMIGHT) {
      ans.push_back(curram_mf);
      swap(a[curram_mf], a[curram_mf + 1]);
      swap(a[curram_mf], a[curram_mf + 2]);
      curram_mf--;
      bool DETROITSMASH = 0;
      for (long long i = 0; i < n; i++)
        if (a[i] != b[i]) DETROITSMASH = 1;
      ALLMIGHT = DETROITSMASH;
    }
  }
  cout << ans.size() << endl;
  for (auto x : ans) cout << x + 1 << " ";
  cout << endl;
  return;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    solve();
  }
}
long long powm(long long a, long long b, long long c = M) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % c;
    a = (a * a) % c;
    b >>= 1;
  }
  return res;
}
long long modI(long long a, long long m = M) {
  long long m0 = m, y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m;
    a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
long long PrimRoot(long long p, long long x) {
  vector<long long> v;
  long long t = p - 1;
  for (long long i = 2; i * i <= t; i++)
    if (t % i == 0) {
      v.push_back((p - 1) / i);
      while (t % i == 0) t /= i;
    }
  if (t > 1) v.push_back((p - 1) / t);
  for (long long i = x + 1; i < p; i++) {
    long long flag = 0;
    for (auto x : v)
      if (powm(i, x, p) == 1) {
        flag = 1;
        break;
      }
    if (flag == 0) return i;
  }
  return 0;
}
void fft(vector<long long>& a, long long n, bool invert, long long m,
         long long x) {
  long long lg_n = __builtin_ctzll(n);
  for (long long i = 0, y = 0; i < n; i++) {
    for (long long j = 0; j < lg_n; j++)
      if ((1LL << j) & i) y |= (1LL << (lg_n - j - 1));
    if (y > i) swap(a[i], a[y]);
  }
  if (invert) x = modI(x, m);
  for (long long s = 2; s <= n; s <<= 1) {
    long long y = powm(x, (n / s), m);
    for (long long j = 0; j < (n / s); j++) {
      long long r = 1;
      for (long long i = 0; i < s / 2; i++) {
        long long u = a[i + j * s], v = (r * a[i + j * s + (s / 2)]) % m;
        a[i + j * s] = (u + v) % m;
        a[i + j * s + (s / 2)] = (u - v + m) % m;
        r = r * y % m;
      }
    }
  }
  if (invert) {
    long long invn = modI(n, m);
    for (long long i = 0; i < n; i++) a[i] = (a[i] * invn) % m;
  }
  return;
}
void PolyMult(vector<long long>& a, vector<long long>& b, vector<long long>& v,
              long long m, long long x) {
  long long n = 1;
  while (n < ((long long)a.size()) + ((long long)b.size())) n <<= 1;
  vector<long long> fa(a.begin(), a.end());
  fa.resize(n, 0);
  vector<long long> fb(b.begin(), b.end());
  fb.resize(n, 0);
  long long y = powm(x, (m - 1) / n, m);
  fft(fa, n, false, m, y);
  fft(fb, n, false, m, y);
  v.resize(n, 0);
  for (long long i = 0; i < n; i++) v[i] = ((fa[i] * fb[i]) % m);
  fft(v, n, true, m, y);
  return;
}