#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const int N = 2E5 + 10, mod = 1E9 + 7;

void solve() {
	int n;
	cin >> n;
	vector a(n, vector<int>(n, 0));

	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < n; j ++) {
			cin >> a[i][j];
		}
	}
	int cnt = 0;
	vector<int> ans;
	for (int i = 0, j; i < n; i ++) {
		if (i % 2) {
			ans.push_back(a[i][n - 1]);
			j = n - 2;
			while (j >= 0) {
				if (a[i][j + 1] > a[i][j]) cnt ++;
				ans.push_back(a[i][j]);
				j --;
			}
		} else {
			ans.push_back(a[i][0]);
			j = 1;
			while (j < n) {
				if (a[i][j - 1] < a[i][j]) cnt ++;
				ans.push_back(a[i][j]);
				j ++;
			}
		}	
	}
	cout << cnt << '\n';
	if (cnt < n * n / 2) {
		reverse(ans.begin(), ans.end());
	}
	for (int i = 0; i < n * n; i ++) {
		cout << ans[i] << " \n"[i == n * n - 1];
	}
} 

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int t = 1;
	cin >> t;
	while (t --) {
		solve();
	}
	return 0;
}