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;
mt19937 rng(230);
inline int randll(int l = INT_MIN, int r = INT_MAX) {
  return uniform_int_distribution<int>(l, r)(rng);
}
struct fenwick {
 public:
  vector<int> t;
  fenwick(int n) { t.assign(n, 0); }
  inline void upd(int i, int first) {
    for (; i < (int)t.size(); i = i | (i + 1)) t[i] += first;
  }
  inline int sum(int r) {
    int ans = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1) ans += t[r];
    return ans;
  }
  inline int sum(int l, int r) { return sum(r) - sum(l - 1); }
};
int main() {
  ios::sync_with_stdio(0);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    fenwick lft(k + k + k + 1), rght(k + k + k + 1);
    for (auto &i : a) cin >> i;
    int ans = n;
    vector<pair<int, int> > b(n / 2);
    for (int i = 0; i < n / 2; i++) {
      b[i] = {a[i] + a[n - 1 - i], i};
      int mx = max(a[i] - 1, a[n - 1 - i] - 1);
      rght.upd(b[i].first - mx, 1);
    }
    sort(b.begin(), b.end());
    int j = 0;
    for (int first = 1; first <= k + k; first++) {
      int f = j;
      while (j < n / 2 && b[j].first <= first) {
        if (b[j].first != first) {
          int mx = max(k - a[b[j].second], k - a[n - 1 - b[j].second]);
          lft.upd(b[j].first + mx, 1);
        }
        int mx = max(a[b[j].second] - 1, a[n - 1 - b[j].second] - 1);
        rght.upd(b[j].first - mx, -1);
        ++j;
      }
      int res = 2 * lft.sum(k + k + k) - lft.sum(first, k + k + k) +
                2 * rght.sum(k + k + k) - rght.sum(0, first);
      ans = min(ans, res);
      int j1 = j - 1;
      for (; f <= j1; f++) {
        int mx = max(k - a[b[f].second], k - a[n - 1 - b[f].second]);
        lft.upd(b[f].first + mx, 1);
      }
    }
    cout << ans << '\n';
  }
}