#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 2005
int a[N][N],n;
int bs9[10][10]=
{
{1,2,1,3,3,4,0,5,5},
{2,1,1,3,4,3,6,6,5},
{2,2,7,7,4,4,6,5,6},
{8,8,7,9,7,9,10,10,11},
{12,8,13,13,9,9,10,11,10},
{8,12,14,13,14,15,15,11,11},
{12,12,13,14,14,16,15,17,17},
{18,18,19,19,16,15,20,20,17},
{18,19,18,19,16,16,20,17,20},
};
int bs11[12][12]=
{
{1,1,2,2,3,3,0,4,4,5,5},
{6,1,7,2,8,3,8,9,4,10,5},
{1,6,2,7,3,8,8,4,9,5,10},
{6,6,7,7,11,11,12,9,9,10,10},
{13,14,13,15,15,11,16,12,17,17,18},
{14,13,13,15,11,16,12,12,17,18,17},
{14,14,19,19,15,16,16,20,20,18,18},
{21,21,22,19,22,23,20,23,20,24,24},
{25,21,19,22,22,23,23,26,26,27,24},
{21,25,28,28,29,29,30,30,26,24,27},
{25,25,28,29,28,29,30,26,30,27,27},
};
int bs13[14][14]=
{
{1,1,2,2,3,3,0,4,4,5,5,6,6},
{7,1,8,2,9,3,9,10,4,11,5,12,6},
{1,7,2,8,3,9,9,4,10,5,11,6,12},
{7,7,8,8,13,13,14,10,10,11,11,12,12},
{15,16,15,17,17,13,18,14,19,19,20,21,21},
{16,15,15,17,13,18,14,14,19,20,19,22,21},
{16,16,23,23,17,18,18,24,24,20,20,21,22},
{25,25,26,23,26,27,24,27,24,28,28,22,22},
{29,25,23,26,26,27,27,30,30,28,31,28,31},
{25,29,32,32,33,33,34,34,30,35,35,31,31},
{29,29,32,33,32,33,34,30,34,36,35,37,37},
{38,38,39,39,40,40,41,41,36,35,42,42,37},
{38,39,38,39,40,41,40,41,36,36,42,37,42},
};
int bs15[16][16]=
{
{1,1,2,2,3,3,0,4,4,5,5,6,6,7,7},
{8,1,9,2,10,3,10,11,4,12,5,13,6,14,7},
{1,8,2,9,3,10,10,4,11,5,12,6,13,7,14},
{8,8,9,9,15,15,16,11,11,12,12,13,13,14,14},
{17,18,17,19,19,15,20,16,21,21,22,22,23,23,24},
{18,17,17,19,15,20,16,16,25,21,26,22,23,24,23},
{18,18,27,27,19,20,20,25,21,26,22,28,28,24,24},
{29,29,30,27,30,31,31,25,25,26,26,32,28,33,33},
{34,29,27,30,30,35,31,35,36,36,37,28,32,38,33},
{29,34,39,40,39,31,35,35,36,37,36,32,32,33,38},
{34,34,40,39,39,41,41,42,42,37,37,43,43,38,38},
{44,44,40,40,45,45,41,46,42,46,47,47,43,48,48},
{49,44,50,50,45,41,45,42,46,46,47,43,47,51,48},
{44,49,52,50,52,53,53,54,54,55,55,56,56,48,51},
{49,49,50,52,52,53,54,53,54,55,56,55,56,51,51},
};
int tbx[16][4]=
{
{1,1,2,3,},
{1,1,2,2,},
{1,2,3,3,},
{1,1,2,2,},
{1,2,3,3,},
{2,3,4,4,},
{3,3,4,4,},
{4,4,5,5,},
{4,4,5,6,},
{5,5,6,7,},
{5,5,6,7,},
{5,6,7,7,},
{6,6,7,7,},
{6,6,7,7,},
};
int tby[16][4]=
{
{1,2,2,1,},
{3,5,4,5,},
{4,3,3,4,},
{6,7,6,8,},
{8,7,7,8,},
{1,2,1,2,},
{5,6,4,6,},
{3,5,3,4,},
{7,8,8,7,},
{1,2,2,1,},
{5,6,6,5,},
{7,8,7,8,},
{1,3,2,3,},
{4,5,4,6,},
};
void work()
{
	cin>>n;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=0;
	if(n%4==0)
	{
		int cnt=0;
		for(int i=1;i<=n;i+=4)
		{
			for(int j=1;j<=n;j+=2)
			{
				cnt++;
				a[i][j]=a[i][j+1]=a[i+1][j]=a[i+2][j+1]=cnt;
				cnt++;
				a[i+1][j+1]=a[i+2][j]=a[i+3][j]=a[i+3][j+1]=cnt;
			}
		}
		printf("%d\n",cnt);
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%d%c",a[i][j]," \n"[j==n]);
	}
	else if(n%2==0)
	{
		int cnt=0;
		for(int i=1;i<=n-2;i+=4)
		{
			for(int j=1;j<=n;j+=2)
			{
				cnt++;
				a[i][j]=a[i][j+1]=a[i+1][j]=a[i+2][j+1]=cnt;
				cnt++;
				a[i+1][j+1]=a[i+2][j]=a[i+3][j]=a[i+3][j+1]=cnt;
			}
		}
		for(int j=1;j<=n-2;j+=4)
		{
			cnt++;
			a[n-1][j]=a[n][j]=a[n-1][j+1]=a[n][j+2]=cnt;
			cnt++;
			a[n][j+1]=a[n-1][j+2]=a[n][j+3]=a[n-1][j+3]=cnt;
		}
		printf("%d\n",cnt);
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%d%c",a[i][j]," \n"[j==n]);
	}
	else
	{
		if(n==1)
		{
			printf("0\n");
			printf("0\n");
			return ;
		}
		if(n==3)
		{
			printf("2\n");
			printf("0 1 1\n");
			printf("2 1 2\n");
			printf("2 2 1\n");
			return ;
		}
		if(n==5)
		{
			printf("5\n");
			printf("1 1 2 2 0\n");
			printf("3 1 4 2 4\n");
			printf("1 3 2 4 4\n");
			printf("3 3 5 0 5\n");
			printf("0 0 0 5 5\n");
			return ;
		}
		if(n==7)
		{
			printf("11\n");
			printf("1 1 2 2 3 3 0\n");
			printf("4 1 5 2 6 3 6\n");
			printf("1 4 2 5 3 6 6\n");
			printf("4 4 5 5 7 7 0\n");
			printf("8 8 0 9 9 7 10\n");
			printf("11 8 11 9 7 10 0\n");
			printf("8 11 11 0 9 10 10\n");
			return ;
		}
		int cnt=0,cur=0;
		if(n%8==1)
		{
			for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) a[i][j]=bs9[i-1][j-1];
			cnt=20,cur=9;
		}
		if(n%8==3)
		{
			for(int i=1;i<=11;i++) for(int j=1;j<=11;j++) a[i][j]=bs11[i-1][j-1];
			cnt=30,cur=11;
		}
		if(n%8==5)
		{
			for(int i=1;i<=13;i++) for(int j=1;j<=13;j++) a[i][j]=bs13[i-1][j-1];
			cnt=42,cur=13;
		}
		if(n%8==7)
		{
			for(int i=1;i<=15;i++) for(int j=1;j<=15;j++) a[i][j]=bs15[i-1][j-1];
			cnt=56,cur=15;
		}
		while(cur<n)
		{
			for(int i=0;i<14;i++)
			{
				cnt++;
				for(int j=0;j<4;j++) a[tbx[i][j]][cur+tby[i][j]]=cnt;
			}
			for(int i=8;i<=cur;i+=2)
			{
				cnt++;
				a[i][cur+1]=a[i+1][cur+1]=a[i][cur+2]=a[i+1][cur+3]=cnt;
				cnt++;
				a[i+1][cur+2]=a[i][cur+3]=a[i][cur+4]=a[i+1][cur+4]=cnt;
				cnt++;
				a[i][cur+5]=a[i+1][cur+5]=a[i][cur+6]=a[i+1][cur+7]=cnt;
				cnt++;
				a[i+1][cur+6]=a[i][cur+7]=a[i][cur+8]=a[i+1][cur+8]=cnt;
			}
			for(int i=0;i<14;i++)
			{
				cnt++;
				for(int j=0;j<4;j++) a[cur+tby[i][j]][tbx[i][j]]=cnt;
			}
			for(int i=8;i<=cur;i+=2)
			{
				cnt++;
				a[cur+1][i]=a[cur+1][i+1]=a[cur+2][i]=a[cur+3][i+1]=cnt;
				cnt++;
				a[cur+2][i+1]=a[cur+3][i]=a[cur+4][i]=a[cur+4][i+1]=cnt;
				cnt++;
				a[cur+5][i]=a[cur+5][i+1]=a[cur+6][i]=a[cur+7][i+1]=cnt;
				cnt++;
				a[cur+6][i+1]=a[cur+7][i]=a[cur+8][i]=a[cur+8][i+1]=cnt;
			}
			for(int i=cur+1;i<=cur+8;i+=4)
			{
				for(int j=cur+1;j<=cur+8;j+=2)
				{
					cnt++;
					a[i][j]=a[i][j+1]=a[i+1][j]=a[i+2][j+1]=cnt;
					cnt++;
					a[i+1][j+1]=a[i+2][j]=a[i+3][j]=a[i+3][j+1]=cnt;
				}
			}
			cur+=8;
		}
		printf("%d\n",cnt);
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%d%c",a[i][j]," \n"[j==n]);
	}
}
signed main()
{
	int T=read(); while(T--) work();
	return 0;
}