#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define mod 10000007
#define F for(int i=0;i<n;i++)
#define raftaar ios_base::sync_with_stdio(false);cin.tie(NULL); 
#define shuru int t;cin>>t;while(t--)
int SieveOfEratosthenes(int n)
{

    bool prime[n + 1];int c=0;
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++)
    {
      
        if (prime[p] == true)
        {
            
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    for (int p = 2; p <= n; p++){
        if (prime[p]) c++;}
        return c;
}

signed main() {
    // shuru{
    // int c=0;
       string s;cin>>s;string a;
       reverse(s.begin(),s.end());
       for(int i=0;i<s.size();i++){
           if(s[i]=='9') s[i]='6';
           else if(s[i]=='6') s[i]='9';
           else continue;
       }
       cout<<s<<endl;
}



#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define mp make_pair
#define fr first
#define sc second

int n;
int p[502];
vector<int> ret;

void add(int i){
	ret.push_back(i);
	swap(p[i],p[i+1]);
}

void solve(int k){
	//cerr<<k<<" "<<ret.size()<<endl;
	if(k==1)return;
	if(k==2){
		if(p[0]!=0)add(0);
		return;
	}
	if(k==3){
		while(p[2]!=2){
			add(0);
			add(1);
		}
		solve(2);
		return;
	}
	int loc=0;
	for(int i=0;i<k;i++){
		if(p[i]==k-1){
			loc=i;
			break;
		}
	}
	if(loc==k-1){
		solve(k-1);
		return;
	}
	if(loc%2==0){
		while(loc!=k-1){
			add(loc);
			loc++;
		}
		if(ret.size()%2!=0)add(1);
		solve(k-1);
		return;
	}
	else {
		if(loc>=3)add(loc-3);
		else add(loc+1);
		while(loc!=k-1){
			add(loc);
			loc++;
		}
		if(ret.size()%2!=0)add(1);
		solve(k-1);
		return;
	}
}

int main(){
	int T;
	scanf("%d",&T);
	for(;T>0;T--){
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%d",&p[i]); p[i]--;
		}
		ret.clear();
		solve(n);
		printf("%d\n",(int)ret.size());
		if(ret.size()==0)puts("");
		else {
			for(int i=0;i<ret.size();i++){
				printf("%d%c",ret[i]+1,(i+1==ret.size())?'\n':' ');
			}
		}
	}
}