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;
const int N = 505;
int a[N];
vector<int> command;
void operate(int i) {
  assert(i >= 0);
  int a0 = a[i + 2];
  a[i + 2] = a[i + 1], a[i + 1] = a[i], a[i] = a0;
  command.push_back(i + 1);
}
int n;
void move_f_t(int f, int t) {
  if (f == t) return;
  assert(t <= f);
  if (f - t == 1) {
    operate(t);
    move_f_t(f + 1, t);
    return;
  }
  operate(f - 2);
  move_f_t(f - 2, t);
}
int find_ind(int v, int i) {
  for (; i < N; ++i) {
    if (a[i] == v) return i;
  }
  assert(0);
}
bool vis[N];
int st[N];
void solve2() {
  command.clear();
  for (int i = 1; i < N; ++i) vis[i] = false;
  scanf("%d ", &n);
  int val = -1;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    st[i] = a[i];
    if (vis[a[i]]) {
      val = a[i];
    }
    vis[a[i]] = true;
  }
  sort(st, st + n);
  int tind;
  if (val != -1) {
    for (int i = 0; i < n; ++i) {
      if (st[i] == val) {
        for (int j = i + 2; j < n; ++j) {
          st[j - 2] = st[j];
        }
        st[n - 2] = st[n - 1] = val;
        tind = i;
        break;
      }
    }
  }
  for (int i = 0; i < n - 2; ++i) {
    int ind = find_ind(st[i], i);
    move_f_t(ind, i);
  }
  if (val == -1) {
    for (int i = 0; i < 3; ++i) {
      bool ig = true;
      for (int j = n - 3; j < n; ++j) {
        if (st[j] != a[j]) ig = false;
      }
      if (ig) break;
      operate(n - 3);
    }
  } else {
    int ind = tind;
    if (ind % 2 == (n - 2) % 2) {
      move_f_t(n - 2, ind);
      assert(a[n - 1] == val);
      move_f_t(n - 1, ind + 1);
    } else {
      move_f_t(n - 1, ind);
      assert(a[n - 1] == val);
      move_f_t(n - 1, ind);
    }
  }
  sort(st, st + n);
  for (int i = 0; i < n; ++i) {
    if (a[i] != st[i]) {
      printf("-1\n");
      return;
    }
  }
  printf("%d\n", (int)command.size());
  for (int com : command) printf("%d ", com);
  putchar('\n');
}
void solve() {
  int t;
  cin >> t;
  while (t--) solve2();
}
inline bool exists_test0(const std::string& name);
inline bool exists_test1(const std::string& name);
int main() {
  solve();
  return 0;
}
inline bool exists_test0(const std::string& name) {
  ifstream f(name.c_str());
  return f.good();
}
inline bool exists_test1(const std::string& name) {
  if (FILE* file = fopen(name.c_str(), "r")) {
    fclose(file);
    return true;
  } else {
    return false;
  }
}