#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#include <random>
#include <chrono>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

const int MAX=1e4;

int N;
vector<int> X,Y,R;

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>N;
    X.resize(N);
    Y.resize(N);
    R.resize(N);
    rep(i,N) cin>>X[i]>>Y[i]>>R[i];

    vector<int> ord(N);
    rep(i,N) ord[i]=i;
    sort(all(ord),[&](int a,int b){
        if(X[a]!=X[b]) return X[a]<X[b];
        if(Y[a]!=Y[b]) return Y[a]<Y[b];
        return a<b;
    });

    auto getScore = [](int r,const vector<int> &len)->double{
        int s=(len[0]+len[2]+1)*(len[1]+len[3]+1);
        double p = 1.0-(1.0-min(r,s)/(double)max(r,s))*(1.0-min(r,s)/(double)max(r,s));
        return p;
    };

    vector<vector<int>> length(N,vector<int> (4,0));
    vector<int> completed(N,0);
    int lastChanged=-1;
    for(int t=0;;t++){
        if(lastChanged+4<t) break;
        bool no_changed=true;
        auto duplicated = [&](int a,int b) ->bool{
            if(a==b) return false;
            if(Y[b]+length[b][0]<Y[a]-length[a][2]) return false;
            if(X[b]+length[b][1]<X[a]-length[a][3]) return false;
            if(Y[b]-length[b][2]>Y[a]+length[a][0]) return false;
            if(X[b]-length[b][3]>X[a]+length[a][1]) return false;
            return true;
        };

        for(auto now:ord){
            //if(completed[now]) continue;

            length[now][t%4]++;
            bool outOfRange=false;
            if(t%4==0&&Y[now]+length[now][0]>=MAX) outOfRange=true;
            if(t%4==1&&X[now]+length[now][1]>=MAX) outOfRange=true;
            if(t%4==2&&Y[now]-length[now][2]<0) outOfRange=true;
            if(t%4==3&&X[now]-length[now][3]<0) outOfRange=true;
            if(outOfRange){
                length[now][t%4]--;
                continue;
            }

            /*bool improved=false;
            {
                double nex_p=getScore(R[now],length[now]);
                length[now][t%4]--;
                double pre_p=getScore(R[now],length[now]);
                length[now][t%4]++;
                if(pre_p<=nex_p) improved=true;
            }
            if(improved==false){
                length[now][t%4]--;
                continue;
            }*/

            int s=(length[now][0]+length[now][2]+1)*(length[now][1]+length[now][3]+1);
            if(s>R[now]){
                //completed[now]=1;
                length[now][t%4]--;
                continue;
            }

            bool ok=true;
            for(auto tar:ord){
                if(now==tar) continue;
                if(duplicated(now,tar)){
                    ok=false;
                    break;
                }
            }
            if(ok==false) length[now][t%4]--;
            else no_changed=false;
        }
        if(no_changed==false) lastChanged=t;
    }

    vector<int> A(N),B(N),C(N),D(N);
    rep(i,N){
        A[i]=X[i]-length[i][3];
        B[i]=Y[i]-length[i][2];
        C[i]=X[i]+length[i][1]+1;
        D[i]=Y[i]+length[i][0]+1;
    }

    rep(i,N) cout<<A[i]<<" "<<B[i]<<" "<<C[i]<<" "<<D[i]<<"\n";

    auto calcS = [&](const vector<int> &len)->int{
        return (len[0]+len[2]+1)*(len[1]+len[3]+1);
    };

    //rep(i,N) cout<<i<<": "<<calcS(length[i])<<" "<<R[i]<<" "<<getScore(R[i],length[i])<<"\n";

    return 0;
}
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1010;

int a[N], b[N], n, m, t;
set<int> odd, even;
int res[N * N], cnt;

void swa(int x) {
    res[cnt ++] = x;
    int l = a[x], r = a[x + 1];
    swap(a[x], a[x + 1]);
    swap(b[l], b[r]);
    t ^= 1;
}

void sol(int x, int y) {
    for (int i = x; i < y; i ++)    swa(i);
}

int get(int x, int y) {
    for (int i = y; i < 5; i ++) {
        if (a[i] != x && a[i + 1] != x) return i;
    }
}

int main() {
    int T;
    cin >> T;
    while (T --) {
        cnt = 0;
        t = 1;
        cin >> n;
        for (int i = 1; i <= n; i ++)   {
            cin >> a[i];
            b[a[i]] = i;
        }
        for (int i = n; i >= 5; i --) {
            int x = b[i];
            if (i == x) continue;
            if ((x & 1) ^ t)   {
                int  tt = get(i, t == 0 ? 2 : 1);
                swa(tt);
            }
            sol(x, i);
        }
        if (n >= 4 && a[4] != 4) {
            if ((b[4] & 1) ^ t) {
                if (b[4] == 1)  swa(2);
                else if (b[4] == 2) swa(3);
                else if(b[4] == 3)  swa(2), swa(3);
            }
            sol(b[4], 4);
        }
        if (n >= 3 && a[3] != 3) {
            if ((b[3] & 1) ^ t) {
                if (b[3] == 1)  swa(2);
                else if (b[3] == 2) swa(1), swa(2);
            }
            sol(b[3], 3);
        }
        if (n >= 2 && b[2] == 1) {
            if (t == 1) swa(1);
            else {
                swa(2), swa(1), swa(2), swa(1), swa(2);
            }
        }
        cout << cnt << endl;
        for (int i = 0; i < cnt; i ++)  printf("%d ", res[i]);

        puts("");
    }
    return 0;
}
