#include<iostream>
#include<cassert>
using namespace std;
int N,idx;
int A[2000][2000];
void add(int x,int y)
{
	assert(0<=x&&x<N);
	assert(0<=y&&y<N);
	assert(A[x][y]==0);
	assert(idx>=1);
	A[x][y]=idx;
}
void place(int x,int y,int t)
{
	idx++;
	if(t==0)
	{
		add(x,y);
		add(x,y+1);
		add(x+1,y+1);
		add(x+2,y);
	}
	else if(t==1)
	{
		add(x,y);
		add(x+1,y+1);
		add(x,y+2);
		add(x+1,y+2);
	}
	else if(t==2)
	{
		add(x,y+1);
		add(x+1,y);
		add(x+2,y);
		add(x+2,y+1);
	}
	else if(t==3)
	{
		add(x,y);
		add(x,y+1);
		add(x+1,y);
		add(x+1,y+2);
	}
	else if(t==4)
	{
		add(x,y);
		add(x,y+1);
		add(x+1,y);
		add(x+2,y+1);
	}
	else if(t==5)
	{
		add(x,y+1);
		add(x,y+2);
		add(x+1,y);
		add(x+1,y+2);
	}
	else if(t==6)
	{
		add(x,y);
		add(x+1,y+1);
		add(x+2,y);
		add(x+2,y+1);
	}
	else if(t==7)
	{
		add(x,y);
		add(x,y+2);
		add(x+1,y);
		add(x+1,y+1);
	}
	else assert(false);
}
void solve()
{
	if(N%4==0)
	{
		for(int i=0;i<N;i+=4)
		{
			for(int j=0;j<N;j+=2)
			{
				place(i,j,0);
				place(i+1,j,6);
			}
		}
	}
	else if(N%4==2)
	{
		N-=2;
		solve();
		N+=2;
		for(int i=0;i<N-2;i+=4)
		{
			place(i,N-2,0);
			place(i+1,N-2,6);
			place(N-2,i,3);
			place(N-2,i+1,5);
		}
	}
	else if(N%4==3)
	{
		N-=2;
		solve();
		N+=2;
		for(int i=0;i<N-3;i+=4)
		{
			place(i,N-2,0);
			place(i+1,N-2,6);
			place(N-2,i,3);
			place(N-2,i+1,5);
		}
		place(N-3,N-2,0);
		place(N-2,N-3,3);
	}
	else
	{
		assert(N%4==1);
		if(N==1);
		else if(N==5)
		{
			place(0,0,0);
			place(1,0,6);
			place(0,2,7);
			place(0,3,6);
			place(3,2,1);
		}
		else if(N==9)
		{
			place(7,4,3);
			place(7,1,1);
			place(7,0,7);
			place(6,7,6);
			place(6,5,0);
			place(5,7,0);
			place(5,0,1);
			place(4,3,6);
			place(4,0,0);
			place(3,5,6);
			place(3,2,4);
			place(2,7,6);
			place(2,6,7);
			place(2,4,4);
			place(1,0,6);
			place(0,6,1);
			place(0,5,7);
			place(0,2,1);
			place(0,2,2);
			place(0,0,0);
		}
		else if(N==13)
		{
			place(0,0,0);
			place(1,0,6);
			place(0,2,0);
			place(1,2,6);
			place(11,6,1);
			place(11,5,7);
			place(11,0,1);
			place(10,11,6);
			place(10,9,6);
			place(10,3,6);
			place(10,0,0);
			place(9,11,0);
			place(9,9,0);
			place(9,6,3);
			place(9,2,4);
			place(8,7,0);
			place(8,4,6);
			place(8,0,7);
			place(7,3,4);
			place(6,11,6);
			place(6,9,6);
			place(6,8,7);
			place(6,5,1);
			place(6,5,2);
			place(6,0,4);
			place(5,11,0);
			place(5,1,6);
			place(4,6,1);
			place(4,3,1);
			place(4,3,2);
			place(3,9,6);
			place(3,6,0);
			place(2,11,6);
			place(2,10,7);
			place(2,8,4);
			place(1,4,6);
			place(0,10,1);
			place(0,9,7);
			place(0,6,1);
			place(0,6,2);
			place(0,4,0);
			place(4,0,3);
		}
		else
		{
			assert(N>=17);
			N-=8;
			solve();
			N+=8;
			place(9+N-11,8+N-11,3);
			place(9+N-11,5+N-11,1);
			place(9+N-11,4+N-11,7);
			place(9+N-11,1+N-11,1);
			place(9+N-11,0+N-11,7);
			place(8+N-11,9+N-11,0);
			place(7+N-11,6+N-11,1);
			place(7+N-11,3+N-11,3);
			place(7+N-11,0+N-11,1);
			place(6+N-11,6+N-11,0);
			place(6+N-11,4+N-11,0);
			place(6+N-11,0+N-11,0);
			place(5+N-11,9+N-11,6);
			place(5+N-11,8+N-11,7);
			place(5+N-11,2+N-11,7);
			place(4+N-11,6+N-11,7);
			place(4+N-11,3+N-11,3);
			place(3+N-11,8+N-11,1);
			place(3+N-11,5+N-11,3);
			place(3+N-11,0+N-11,1);
			place(3+N-11,0+N-11,2);
			place(2+N-11,7+N-11,3);
			place(1+N-11,3+N-11,6);
			place(0+N-11,9+N-11,6);
			place(0+N-11,8+N-11,7);
			place(0+N-11,5+N-11,1);
			place(0+N-11,5+N-11,2);
			place(0+N-11,3+N-11,0);
			for(int i=0;i<N-11;i+=2)
			{
				place(i,N-8,3);
				place(i,N-7,5);
				place(i,N-4,3);
				place(i,N-3,5);
				place(N-8,i,0);
				place(N-7,i,6);
				place(N-4,i,0);
				place(N-3,i,6);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;cin>>T;
	for(;T--;)
	{
		cin>>N;
		for(int i=0;i<N;i++)for(int j=0;j<N;j++)A[i][j]=0;
		idx=0;
		solve();
		int cnt=0;
		for(int i=0;i<N;i++)for(int j=0;j<N;j++)if(A[i][j]!=0)cnt++;
		assert(cnt%4==0);
		cnt/=4;
		if(N%2==1&&N>=9)
		{
			assert(N*N/4==cnt);
		}
		cout<<cnt<<"\n";
		for(int i=0;i<N;i++)for(int j=0;j<N;j++)cout<<A[i][j]<<(j+1==N?"\n":" ");
	}
}