#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e3 + 10;
 
int c, n, dx, a[N][N];
 
void put(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)
{
	x1 += dx, x2 += dx, x3 += dx, x4 += dx;
	c++; a[x1][y1] = a[x2][y2] = a[x3][y3] = a[x4][y4] = c;
}

void block24(int i, int j)
{
	// 2 x 4
	put(i, j, i + 1, j, i + 1, j + 1, i, j + 2);
	put(i, j + 1, i + 1, j + 2, i, j + 3, i + 1, j + 3);
}
 
void block42(int i, int j)
{
	// 4 x 2
	put(i, j, i, j + 1, i + 1, j + 1, i + 2, j);
	put(i + 1, j, i + 2, j + 1, i + 3, j, i + 3, j + 1);
}
 
void make_pattern(int n)
{
	if (n < 9)
	{
		assert(n == 5 || n == 7);
		int t = n - 5;
		put(t + 1, t + 4, t + 1, t + 5, t + 2, t + 3, t + 2, t + 5);
		put(t + 1, t + 3, t + 2, t + 4, t + 3, t + 3, t + 3, t + 4);
		put(t + 3, t + 1, t + 3, t + 2, t + 4, t + 1, t + 5, t + 2);
		put(t + 4, t + 2, t + 4, t + 3, t + 5, t + 1, t + 5, t + 3);
		put(t + 3, t + 5, t + 4, t + 4, t + 5, t + 4, t + 5, t + 5);
		if (n == 7) block24(1, 4), block42(4, 1), put(t, t + 1, t + 1, t + 2, t + 2, t + 1, t + 2, t + 2), put(1, 3, 2, 2, 3, 2, 3, 3);
		return;
	}
	if (n == 9)
	{
		block42(1, 1), block24(1, 6), block42(6, 8), block24(8, 1);
		put(1, 4, 1, 5, 2, 3, 2, 5), put(1, 3, 2, 4, 3, 3, 3, 4);
		put(5, 1, 5, 2, 6, 1, 7, 2), put(6, 2, 6, 3, 7, 1, 7, 3);
		put(8, 5, 9, 5, 9, 6, 8, 7), put(7, 6, 7, 7, 8, 6, 9, 7);
		put(3, 8, 4, 9, 5, 8, 5, 9), put(3, 7, 3, 9, 4, 7, 4, 8);
		put(3, 5, 3, 6, 4, 5, 5, 6), put(4, 6, 5, 7, 6, 6, 6, 7);
		put(4, 3, 4, 4, 5, 3, 6, 4), put(5, 4, 6, 5, 7, 4, 7, 5);
		return;
	}
	
	if (n % 4 == 3)
	{
		dx += 2; make_pattern(n - 2); dx -= 2;
		for (int i = 1; i <= n - 3; i += 4) block24(1, i);
		for (int i = n - 3; i >= 4; i -= 4) block42(i, n - 1);
		put(1, n - 2, 1, n - 1, 2, n - 2, 2, n), put(1, n, 2, n - 1, 3, n - 1, 3, n);
	}
	else
	{
		dx += 2; make_pattern(n - 4); dx -= 2;
		for (int i = 1; i <= n - 5; i += 4) block24(1, i), block24(n - 1, i);
		put(1, n - 4, 1, n - 3, 2, n - 4, 3, n - 3), put(2, n - 3, 3, n - 2, 4, n - 3, 4, n - 2);
		put(1, n - 2, 1, n - 1, 2, n - 2, 2, n), put(1, n, 2, n - 1, 3, n - 1, 3, n);
		for (int i = 4; i <= n - 6; i += 4) block42(i, n - 1), block42(i + 1, n - 3);
		put(n - 5, n - 1, n - 5, n, n - 4, n - 2, n - 4, n), put(n - 4, n - 3, n - 4, n - 1, n - 3, n - 3, n - 3, n - 2);
		block42(n - 3, n - 1);
		put(n - 2, n - 3, n - 2, n - 2, n - 1, n - 3, n, n - 2), put(n - 1, n - 4, n - 1, n - 2, n, n - 4, n, n - 3); 
	}
}
 
void solve()
{
	cin >> n;
	if (n <= 3)
	{
		if (n == 1) cout << "0\n0\n";
		else if (n == 2) cout << "0\n0 0\n0 0\n";
		else if (n == 3) cout << "2\n2 1 2\n1 2 2\n1 1 0\n";
		return;
	}
	
	c = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a[i][j] = 0;
			
	if (n % 2 == 0)
	{
		for (int i = 1; i <= n; i += 2)
			for (int j = 1; j + 4 - 1 <= n; j += 4)
				block24(i, j);
		if (n % 4 == 2)
			for (int i = 1; i + 4 - 1 <= n; i += 4)
				block42(i, n - 1);
	}
	else make_pattern(n);
	
	cout << c << '\n';
	for (int i = 1; i <= n; i++, cout << '\n')
		for (int j = 1; j <= n; j++)
			cout << a[i][j] << '\t';
}
 
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	
	int t; cin >> t;
	while (t--) solve();
}