#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e3 + 10;
 
int c, n, a[N][N];
 
void block24(int i, int j)
{
	// 2 x 4
	c++;
	a[i][j] = a[i + 1][j] = a[i + 1][j + 1] = a[i][j + 2] = c;
	c++;
	a[i][j + 1] = a[i + 1][j + 2] = a[i][j + 3] = a[i + 1][j + 3] = c;
}
 
void block42(int i, int j)
{
	// 4 x 2
	c++;
	a[i][j] = a[i][j + 1] = a[i + 1][j + 1] = a[i + 2][j] = c;
	c++;
	a[i + 1][j] = a[i + 2][j + 1] = a[i + 3][j] = a[i + 3][j + 1] = c;
}
 
void put(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)
{
	c++; a[x1][y1] = a[x2][y2] = a[x3][y3] = a[x4][y4] = c;
}
 
void make_pattern(int n)
{
	if (n == 1) return;
	if (n == 3)
	{
		put(1, 3, 2, 2, 3, 2, 3, 3);
		return;
	}
    make_pattern(n - 4);
    for (int i = 1; i <= n - 5; i += 2) block24(i, n - 3);
    for (int j = 1; j <= n - 5; j += 2) block42(n - 3, j);
    int t = n - 5;
    if (n > 5) put(t, t + 1, t + 1, t + 2, t + 2, t + 1, t + 2, t + 2);
    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);
}
 
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;
	}
	if (n == 9)
	{
		cout << "20\n";
		cout << "2	1	1	12	12	15	13	11	13\n1	2	1	12	15	12	13	13	11\n2	2	14	14	15	15	0	11	11\n17	14	17	14	16	16	10	10	9\n17	17	18	18	16	20	10	9	10\n3	3	18	19	19	16	20	9	9\n3	4	19	18	19	20	20	7	7\n4	3	5	6	5	6	8	7	8\n4	4	5	5	6	6	8	8	7\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] << ' ';
}
 
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	
	int t; cin >> t;
	while (t--) solve();
}