#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
    int n;
    cin >>n;
    int a[n+1];
    for (int i = 0; i < n; i++) cin >>a[i];
    int buckets[1001] = {0};
    for (int i = 0; i < n; i++) {
        for (int k = 2; k <= 1000; k++) {
            if (a[i]%k==0){
                buckets[k]++;
            }
        }
    }
    int tmp=0,ans=0;
    for (int k = 2; k <= 1000; k++) {
        if(buckets[k]>=tmp) {
            tmp=buckets[k];
            ans=k;
        }
    }
    cout << ans << endl; 
}

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

int n; vector<int> ans;

const int MAX=5e2+7;

int s[MAX],p[MAX];

void opt (int pos) {
	swap(p[s[pos]],p[s[pos+1]]);
	swap(s[pos],s[pos+1]);
	ans.push_back(pos);
	return;
}

void solve (int p1,int p2,int p3) {
	while (!(s[p1]<s[p2]&&s[p2]<s[p3])) {
		if (ans.size()%2==p1%2) opt(p2);
		else opt(p1);
	} return;
}

void solve () {
	
	scanf("%d",&n); ans.clear();
	for (int i=1;i<=n;i++)
		scanf("%d",&s[i]),p[s[i]]=i;
	
	if (n==1) { puts("0"); return; }
	if (n==2) {
		if (s[1]>s[2]) puts("1"),puts("1");
		else puts("0");
		return;
	}
	if (n==3) solve(1,2,3);
	
	const int odd=n&1?n-2:n-1;
	const int eve=n&1?n-1:n-2;
	
	for (int i=1;i<=n-3;i++) {
		rst:
		if (p[i]&1) {
			if (ans.size()%2==0)
				{ opt(odd); goto rst; }
			for (int t=p[i]-1;t>=i;t--)
				opt(t);
		} else {
			if (ans.size()%2==1)
				{ opt(eve); goto rst; }
			for (int t=p[i]-1;t>=i;t--)
				opt(t);
		}
	}
	
	solve(n-2,n-1,n);
	
	printf("%d\n",ans.size());
	for (auto cur:ans)
		printf("%d ",cur);
	printf("\n");
	
	return;
		
}

int main () {
	
	int T; scanf("%d",&T);
	while (T--) solve();
	
	return 0;
}