/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n;
int ans[2005][2005],idx;
void fill1(int x1,int y1)
{
	idx++;
	ans[x1][y1]=ans[x1][y1+1]=ans[x1+1][y1]=ans[x1+1][y1+2]=idx;
	idx++;
	ans[x1+1][y1+1]=ans[x1][y1+2]=ans[x1][y1+3]=ans[x1+1][y1+3]=idx;
}
void fill2(int x1,int y1)
{
	idx++;
	ans[x1][y1]=ans[x1][y1+1]=ans[x1+1][y1]=ans[x1+2][y1+1]=idx;
	idx++;
	ans[x1+1][y1+1]=ans[x1+2][y1]=ans[x1+3][y1]=ans[x1+3][y1+1]=idx;
}
void print()
{
	cout<<idx<<"\n";
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cout<<ans[i][j]<<(j==n?"\n":" ");
//		for(int j=1;j<=n;j++) cout<<left<<setw(4)<<ans[i][j]<<" ";
//		cout<<"\n";
	}
}
int ans5[5][5]={
	{0,4,4,0,0},
	{5,4,5,3,3},
	{5,5,4,3,0},
	{1,1,2,2,3},
	{1,2,1,2,0}
};
int ans9[9][9]={
	{1,2,1,2,19,19,20,18,18},
{1,1,2,2,19,20,19,17,18},
{3,4,4,6,6,20,20,18,17},
{4,3,4,5,6,11,11,17,17},
{3,3,5,6,0,12,11,16,16},
{7,7,5,5,12,11,15,16,15},
{8,7,9,9,12,12,15,15,16},
{7,8,9,10,10,13,13,14,14},
{8,8,10,9,10,13,14,13,14}
};
void solve()
{
	
	cin>>n;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i][j]=0;
	idx=0;
	if(n==1)
	{
		cout<<"0\n0\n";
		return;
	}
	if(n==2)
	{
		cout<<"0\n0 0\n0 0\n";
		return;
	}
	if(n==3)
	{
		cout<<"2\n0 1 1\n2 2 1\n2 1 2\n";
		return;
	}
	int flg=0;
	if(n==5||n==7)
	{
		if(n==7) flg=1,n-=2;
		idx=5;
		for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) ans[i][j]=ans5[i-1][j-1];
		if(flg)
		{
			for(int i=1;i<n;i+=4) fill1(n+1,i),fill2(i,n+1);
		
			idx++;
			ans[n+1][n]=ans[n+2][n]=ans[n+2][n+1]=ans[n+1][n+2]=idx;
			idx++;
			ans[n][n+1]=ans[n][n+2]=ans[n+1][n+1]=ans[n+2][n+2]=idx;
			n+=2;
		}
		print();
		return;
	}
	if(n%2==0)
	{
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i%2==1&&j%4==1&&i+1<=n&&j+3<=n) fill1(i,j);
		if(n%4==2) 
		{
			for(int i=1;i+3<=n;i+=4) fill1(n-1,i),fill2(i,n-1);
		}
		print();
		return;
	}
	
	if(n%4==3) flg=1,n-=2;
	int st=(n+1)/2-4;
	idx=20;
	for(int i=0;i<9;i++) for(int j=0;j<9;j++) ans[st+i][1+j]=ans9[i][j];
	for(int i=9,L=st,R=st+8;i<n;i+=4,L-=2,R+=2)
	{
		idx++;
		int x=R,y=i;
		ans[x+1][y]=ans[x+2][y]=ans[x+2][y+1]=ans[x+1][y+2]=idx;
		idx++;
		ans[x][y+1]=ans[x][y+2]=ans[x+1][y+1]=ans[x+2][y+2]=idx;
		
		idx++;
		x=L,y=i;
		ans[x-2][y]=ans[x-2][y+1]=ans[x-1][y]=ans[x][y+1]=idx;
		idx++;
		ans[x-1][y+1]=ans[x][y+2]=ans[x+1][y+1]=ans[x+1][y+2]=idx;
		
		idx++;
		ans[x+3][y+1]=ans[x+3][y+2]=ans[x+2][y+1]=ans[x+2][y+3]=idx;
		idx++;
		ans[x+2][y+2]=ans[x+2][y+4]=ans[x+1][y+3]=ans[x+1][y+4]=idx;
		
		idx++;
		ans[x-2][y+2]=ans[x-2][y+3]=ans[x-1][y+2]=ans[x-1][y+4]=idx;
		idx++;
		ans[x-2][y+4]=ans[x-1][y+3]=ans[x][y+3]=ans[x][y+4]=idx;
		for(int j=1;j<i;j+=4) fill1(L-2,j),fill1(R+1,j);
		for(int j=L+4;ans[j][i+1]==0;j+=4) fill2(j,i+1);
		for(int j=L+3;j<=R;j+=4) fill2(j,i+3);
	}
	if(flg) 
	{
		for(int i=1;i<n;i+=4) fill1(n+1,i),fill2(i,n+1);
		
		idx++;
		ans[n+1][n]=ans[n+2][n]=ans[n+2][n+1]=ans[n+1][n+2]=idx;
		idx++;
		ans[n][n+1]=ans[n][n+2]=ans[n+1][n+1]=ans[n+2][n+2]=idx;
		n+=2;
	}
	print();
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}