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;
long long power(long long x, long long y);
long long mpower(long long x, long long y, long long p);
long long modInv(long long a, long long m);
long long gcdExtended(long long a, long long b, long long *x, long long *y);
bool isPrime(long long n);
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t, i, j, k, l, h, p, q, r, x, y, z, a, b, c, d, f, n, m,
      M = 1000000007;
  char ch, ch2, ch3;
  string s, s1, s2, s3;
  vector<long long> v, w;
  set<long long> S;
  cin >> t;
  while (t--) {
    unordered_map<long long, long long> N;
    cin >> n >> k;
    long long A[n];
    for (i = 0; i < n; i++) {
      cin >> A[i];
    }
    p = 2 * k + 5;
    long long X[p];
    for (i = 0; i < p; i++) {
      X[i] = 0;
    }
    q = n / 2;
    for (i = 0; i < q; i++) {
      a = A[i] + A[n - i - 1];
      x = a - max(A[i], A[n - i - 1]) + 1;
      y = a + k - min(A[i], A[n - i - 1]);
      X[0] += 2;
      X[x] -= 2;
      X[x] += 1;
      X[a] -= 1;
      X[a + 1] += 1;
      X[y + 1] -= 1;
      X[y + 1] += 2;
    }
    for (i = 1; i < p; i++) {
      X[i] += X[i - 1];
    }
    x = LLONG_MAX;
    for (i = 0; i < p; i++) {
      x = min(x, X[i]);
    }
    cout << x << "\n";
  }
  return 0;
}
long long modInv(long long a, long long m) {
  long long x, y;
  long long g = gcdExtended(a, m, &x, &y);
  long long res = (x % m + m) % m;
  return res;
}
long long gcdExtended(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long x1, y1;
  long long gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
long long mpower(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long power(long long x, long long y) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = res * x;
    y = y >> 1;
    x = x * x;
  }
  return res;
}
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  long long p = sqrt(n);
  for (int i = 5; i <= p; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}