#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> ar(n);
        for (auto& v: ar) {
            cin >> v;
            v--;
        }
        if (n == 3 && ar[0] == 0 && ar[1] == 2 && ar[2] == 1) {
            cout << 5 << endl;
            cout << "1 2 1 2 1" << endl;
            continue;
        }
        vector<int> where(n);
        for (int i = 0; i < n; ++i) {
            where[ar[i]] = i;
        }
        int move = 0;
        vector<int> ans;
        // for (auto v: ar) {
        //     cout << v << " ";
        // }
        // cout << "| " << move << endl;
        int who = -1;
        for (int i = 0; i < n; ++i) {
            if (where[i] == i) continue;
            while (((where[i] - 1) ^ move) & 1) {
                if ((i ^ move) & 1) {
                    if (i + 1 >= n - 1) {
                        ans.push_back(move & 1);
                        who = move & 1;
                        swap(ar[move & 1], ar[(move & 1) + 1]);
                    } else {
                        swap(ar[i + 1], ar[i + 2]);
                        where[ar[i + 1]] = i + 1;
                        where[ar[i + 2]] = i + 2;
                        ans.push_back(i + 1);
                    }
                } else {
                    assert(i < n - 1);
                    swap(ar[i], ar[i + 1]);
                    where[ar[i]] = i;
                    where[ar[i + 1]] = i + 1;
                    ans.push_back(i);
                }
                move++;
                // for (auto v: ar) {
                //     cout << v << " ";
                // }
                // cout << "| " << move << endl;
            }
            while (where[i] > i) {
                ans.push_back(where[i] - 1);
                swap(ar[where[i] - 1], ar[where[i]]);
                where[ar[where[i]]] = where[i];
                where[i]--;
                move++;
                // for (auto v: ar) {
                //     cout << v << " ";
                // }
                // cout << "| " << move << endl;
            }
        }
        if (who != -1) {
            assert(((who ^ move) & 1) == 0);
            ans.push_back(who);
            swap(ar[who], ar[who + 1]);
            move++;
        }
        if (n == 4 && ar[0] == 0 && ar[1] == 2 && ar[2] == 3 && ar[3] == 1) {
            ans.push_back(2);
            swap(ar[2], ar[3]);
            ans.push_back(1);
            swap(ar[1], ar[2]);
            move += 2;
        }
        assert(move <= n * n);
        // cout << endl << endl;
        // for (auto v: ar) {
        //     cout << v << " ";
        // }
        // cout << endl;
        for (int i = 0; i < n; ++i) {
            assert(ar[i] == i);
        }
        cout << ans.size() << endl;
        for (auto v: ans) {
            cout << v + 1 << " ";
        }
        cout << endl;
    }
}

#include<bits/stdc++.h>
typedef uint32_t uint;
typedef uint64_t u64;
typedef int64_t i64;
typedef long double f128;
using namespace std;

void scan(){}

template<typename T,class... Args>
void scan(T& n,Args&... args){
  cin>>n;
  scan(args...);
}

template<typename T>
void scan_vec(T start,T end){
  T now=start;
  for(;now!=end;++now){
    cin>>(*now);
  }
}

void print(){}

template<typename T,class... Args>
void print(T n,Args... args){
  cout<<n;
  print(args...);
}

template<typename T>
void println(T n){
  cout<<n<<endl;
}

template<typename T,class... Args>
void println(T n,Args... args){
  cout<<n<<' ';
  println(args...);
}

template<typename T>
void print_vec(T start,T end){
  if(start!=end){
    T now=start;
    cout<<(*now);
    ++now;
    for(;now!=end;++now){
      cout<<' '<<(*now);
    }
  }
  cout<<endl;
}

pair<vector<int>,vector<int>> solve(){
  random_device seed_gen;
  mt19937 engine(seed_gen());
  int N;
  scan(N);
  vector<int> p(N);
  scan_vec(p.begin(),p.end());
  for(int i=0;i<N;++i){
    p[i]-=1;
  }
  int invcnt=0;
  for(int i=0;i<N;++i){
    for(int j=i+1;j<N;++j){
      if(p[i]>p[j]){
        ++invcnt;
      }
    }
  }
  while(1){
    vector<int> vec=p;
    int cnt=invcnt;
    vector<int> ans;
    for(int i=0;i<N*N;++i){
      if(cnt==0){
        println(ans.size());
        print_vec(ans.begin(),ans.end());
        return {vec,ans};
      }
      bool is_swap=0;
      for(int j=i%2;j<N-1;j+=2){
        if(vec[j]>vec[j+1]){
          swap(vec[j],vec[j+1]);
          ans.push_back(j+1);
          --cnt;
          is_swap=1;
          break;
        }
      }
      if(is_swap){
        continue;
      }
      if(i%2==0){
        uint n=engine()%(N/2);
        swap(vec[2*n],vec[2*n+1]);
        ++cnt;
        ans.push_back(2*n+1);
      }
      else{
        uint n=engine()%((N-1)/2);
        swap(vec[2*n+1],vec[2*n+2]);
        ++cnt;
        ans.push_back(2*n+2);
      }
    }
  }
}

int main(){
  int T;
  scan(T);
  for(int i=0;i<T;++i){
    solve();
  }
  return 0;
}