#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#define int ll

const int N = 1e6;
int tn, n, p[N];
vector<int> ans;

bool can(int i) {
	assert(1 <= i && i < n);
	return (int)ans.size() % 2 == (i - 1) % 2;
}
void sh(int i) {
	assert(can(i));
	ans.emplace_back(i);
	swap(p[i - 1], p[i]);
}
// 1 2 3
// 2 1 3
// 2 3 1
// 3 2 1
// 3 1 2
// 1 3 2

void lo(int i) {
	assert(!can(i));
	if (i >= 2) {
		sh(i - 1), sh(i), sh(i - 1), sh(i), sh(i - 1);
	} else {
		sh(i + 1), sh(i), sh(i + 1), sh(i), sh(i + 1);
	}
}

void x2(int i) {
	assert(!can(i));
	assert(i >= 2);
	sh(i - 1), sh(i), sh(i - 1), sh(i);
}

void print() {
	for (int j = 0; j < n; ++j) {
		cout << p[j] << " ";
	}
	cout << endl;
}

void solve() {
	if (n == 2) {
		if (p[0] > p[1]) {
			assert(can(1));
			sh(1);
		}
		return;
	}
	// for (int i = 0; i < n; ++i) {
	// 	cout << p[i] << " ";
	// }
	// cout << endl;
	for (int from = 1; from < n; ++from) {
		int i = from;
		if (p[i] >= p[i - 1]) {
			continue;
		}
		// cout << "st " << i << endl;
		if (!can(i)) {
			if (can(n - 1)) {
				sh(n - 1);
			} else if (from != n - 1) {
				assert(can(n - 2));
				sh(n - 2);
			}
		}
		// print();
		while (i && p[i] < p[i - 1]) {
			if (can(i)) {
				sh(i);
			} else if (i >= 2 && p[i] < p[i - 2]) {
				x2(i);
				--i;
			} else {
				lo(i);
			}
			--i;
		}
		// print();
	}
	assert(is_sorted(p, p + n));
	assert((int)ans.size() <= n * n);
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> tn;
	while (tn--) {
		cin >> n;
		for (int i = 0; i < n; ++i) {
			cin >> p[i];
		}
		ans.clear();
		solve();
		cout << ans.size() << "\n";
		for (int e : ans) {
			cout << e << " ";
		}
		cout << "\n";
	}
	return 0;
}
#include <bits/stdc++.h>
using namespace std;

// Type alias
using ll=long long;
using ld=double;

using pi=pair<int,int>;
using pll=pair<ll,ll>;
using pld=pair<ld,ld>;
using ti3=tuple<int, int, int>;

using vi=vector<int>;
using vll=vector<ll>;
using vld=vector<ld>;
using vpi=vector<pi>;
using vpll=vector<ll>;
using vpld=vector<ld>;
using vti3=vector<ti3>;

// Constants
const double EPS = 1e-9;
const int inf = numeric_limits<int>::max() / 2;
const ll mod = 1e9+7;

// Macro
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rrep(i,n) for(int i=int(n-1);i>=0;--i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(i,a,b) for(int i=int(b-1);i>=int(a);--i)
#define SHOW(a) cout << #a << " = " << a << endl
#define ARR(a,n) for(int i=0;i<int(n);++i) cout << #a << "[" << i << "]" << " = " << a[i] << endl

#define ALL(a) a.begin(),a.end()

// Funtcions
ll pow(ll base, ll i, ll mod){
  ll a = 1;
  while(i){
    if (i & 1) {
      a *= base;
      a %= mod;
    }
    base *= base;
    base %= mod;
    i >>= 1;
  }
  return a;
}
ll gcd(ll a, ll b){
  while(b){
    ll c = a % b;
    a = b;
    b = c;
  }
  return a;
}
ll lcm(ll a, ll b){
  return a / gcd(a, b) * b;
}
template<typename T> bool chmin(T& a, const T& b) {
  if (a > b) return a = b, true; else return false;
}

template<typename T> bool chmax(T& a, const T& b) {
  if (a < b) return a = b, true; else return false;
}


void solve(){
  int n; cin >> n;
  vi p(n);
  rep(i, n) cin >> p[i];

  vi ans;
  int i = 1;
  bool isodd = false;
  int even = (n - 1) - (n % 2) - 1;
  int odd = (n - 1) - !(n % 2) - 1;
  while(i < n - 1) {
    int idx = find(ALL(p), i) - p.begin();
    if(i - 1 == idx) {
      i++;
      continue;
    }
    if((idx - 1) % 2 != isodd) {
      if(isodd) {
        ans.push_back(odd + 1);
        swap(p[odd], p[odd+1]);
      } else {
        ans.push_back(even + 1);
        swap(p[even], p[even+1]);
      }
    } else {
      ans.push_back(idx);
      swap(p[idx - 1], p[idx]);
    }
    isodd ^= true;
  }

  if(p[n - 1] == n - 1) {
    if(isodd == (n - 2) % 2) {
      ans.push_back(n - 1);
    } else {
    ans.push_back(n - 2);
    ans.push_back(n - 1);
    ans.push_back(n - 2);
    ans.push_back(n - 1);
    ans.push_back(n - 2);
    }
  }

  cout << ans.size() << endl;
  rep(i, ans.size()) {
    if(i != 0) cout << " ";
    cout << ans[i];
  }
  cout << endl;
}

int main(){
// FastIO
//ios_base::sync_with_stdio(false);
cin.tie(NULL);
  ll t;
  cin >> t;
  rep(ghrskj, t) solve();
  return 0;
}