#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<pii>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=5010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int t, n, cnt;
int a[N][N];

void postavi (vi v) {
	cnt++;
	for (auto pp : v) {
		int x = pp.first, y = pp.second;
		a[x][y] = cnt;
	}
}

void hor (int x, int y) {
	postavi({{x, y}, {x + 1, y}, {x, y + 1}, {x + 1, y + 2}});
	postavi({{x + 1, y + 1}, {x + 1, y + 3}, {x, y + 2}, {x, y + 3}});
}

void ver (int x, int y) {
	postavi({{x, y}, {x, y + 1}, {x + 1, y + 1}, {x + 2, y}});
	postavi({{x + 1, y}, {x + 2, y + 1}, {x + 3, y}, {x + 3, y + 1}});
}

void tri (int x, int y, int s) {
	postavi({{x, y}, {x + 1 * s, y + 1 * s}, {x + 1 * s, y + 2 * s}, {x, y + 2 * s}});
	postavi({{x, y + 1 * s}, {x + 1 * s, y}, {x + 2 * s, y}, {x + 2 * s, y + 1 * s}});
}

void ispis () {
	cout << cnt << '\n';
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << a[i][j];
			if (j < n-1) cout << " ";
		}
		cout << '\n';
	}
}

void solve () {
	int ax = 0, ay = 0;
	int bx = n - 3, by = n - 1;
	for (int br = n / 4 - 1; br >= 1; br--) {
		tri(ax, ay, 1);
		for (int i = 0; i < br; i++) {
			hor(ax, ay + 3 + 4 * i);
			ver(ax + 3 + 4 * i, ay);
		}
		tri(bx, by, -1);
		for (int i = 0; i < br; i++) {
			hor(bx - 1, by - 2 - 4 * (i + 1));
			ver(bx - 2 - 4 * (i + 1), by - 1);
		}
		
		ax += 2; ay += 2;
		bx -= 2; by -= 2;
	}
	tri(ax, ay, 1);
	postavi({{bx, by}, {bx - 1, by - 1}, {bx - 2, by - 1}, {bx - 2, by}});
	for (int i = 0; i < n - 1; i += 4) {
		hor(n - 2, i);
	}
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while (t--) {
		cin >> n;

		cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				a[i][j] = 0;
			}
		}

		if (n == 1) {
		} else if (n == 3) {
			tri(0, 0, 1);
		} else if (n % 4 == 0) {
			for (int i = 0; i < n; i += 2) {
				for (int j = 0; j < n; j += 4) {
					hor(i, j);
				}
			}
		} else if (n % 4 == 2) {
			for (int i = 0; i < n - 2; i += 2) {
				for (int j = 0; j < n - 2; j += 4) {
					hor(i, j);
				}
			}
			for (int i = 0; i < n - 2; i += 4) {
				hor(n - 2, i);
				ver(i, n - 2);
			}
		} else if (n % 4 == 1) {
			solve();
		} else if (n % 4 == 3) {
			n -= 2;
			solve();
			n += 2;
			int bx = n - 1, by = n - 1;
			tri(bx, by, -1);
			int br = n / 4;
			for (int i = 0; i < br; i++) {
				hor(bx - 1, by - 2 - 4 * (i + 1));
				ver(bx - 2 - 4 * (i + 1), by - 1);
			}
		}
		ispis();
	}
	return 0;
}