#include<bits/stdc++.h>
//=========================================================
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
#define pd push_back
#define all(x) x.begin(),x.end()
#define allA(x,l,r) x+l,x+r+1
#define mpr std::make_pair
#define ve std::vector
#define mpre(v) v.insert(v.begin(),0)
#define lb lower_bound
//=========================================================
namespace Balance_tree{
	struct Mes{
		Mes(){}
		friend Mes operator + (Mes A,Mes B){
			Mes ans;
			return ans;
		}
	};
	const int N=2e5+10;
	std::mt19937 rnd(time(NULL));
	struct Mes_BLT{
		struct node{int l,r;ll val;int key,sz;Mes rv,v;}tr[5];//don't forget to promote it
		int rot,cnt=0;
		std::vector<int> bin;
		void pushup(int rt){tr[rt].sz=tr[tr[rt].l].sz+tr[tr[rt].r].sz+1;
			if(tr[rt].l&&tr[rt].r)tr[rt].rv=tr[tr[rt].l].rv+tr[rt].v+tr[tr[rt].r].rv;
			else if(tr[rt].l)tr[rt].rv=tr[tr[rt].l].rv+tr[rt].v;
			else if(tr[rt].r)tr[rt].rv=tr[rt].v+tr[tr[rt].r].v;}
		int newid(){
			if(bin.empty())return ++cnt;
			int x=bin.back();bin.pop_back();
			return x;
		}void split(int rt,ll val,int &x,int &y){
			if(!rt)return x=y=0,void();
			if(tr[rt].val<=val)x=rt,split(tr[rt].r,val,tr[rt].r,y);
			else y=rt,split(tr[rt].l,val,x,tr[rt].l);
			pushup(rt);
		}int merge(int x,int y){
			if(!x||!y)return x|y;
			if(tr[x].key<=tr[y].key)
				return tr[x].r=merge(tr[x].r,y),pushup(x),x;
			else return tr[y].l=merge(x,tr[y].l),pushup(y),y;
		}int build(int val,Mes P){int id=newid();return tr[id]={0,0,val,int(rnd()),1,P,P},id;}
		void insert(ll val,Mes P){
			int x,y;split(rot,val,x,y);
			rot=merge(merge(x,build(val,P)),y);
		}void del(ll val){
			int x,y,z;split(rot,val,x,z);
			split(x,val-1,x,y);bin.pd(y);
			rot=merge(merge(x,merge(tr[y].l,tr[y].r)),z);
		}Mes query(ll l,ll r){
			int x,y,z;split(rot,r,x,z);
			split(x,l-1,x,y);
			Mes ans=tr[y].rv;
			rot=merge(merge(x,y),z);
			return ans;
		}
		void clear(){for(int i=1;i<=cnt;i++)tr[i]={0,0,0,0,0,Mes(),Mes()};cnt=rot=0;bin.clear();}
	};
	struct Basic_BLT{
		struct node{int l,r;ll val;int key,sz;}tr[5];//don't forget to promote it
		int rot,cnt=0;
		std::vector<int> bin;
		void pushup(int rt){tr[rt].sz=tr[tr[rt].l].sz+tr[tr[rt].r].sz+1;}
		int newid(){
			if(bin.empty())return ++cnt;
			int x=bin.back();bin.pop_back();
			return x;
		}void split(int rt,int val,int &x,int &y){
			if(!rt)return x=y=0,void();
			if(tr[rt].val<=val)x=rt,split(tr[rt].r,val,tr[rt].r,y);
			else y=rt,split(tr[rt].l,val,x,tr[rt].l);
			pushup(rt);
		}int merge(int x,int y){
			if(!x||!y)return x|y;
			if(tr[x].key<=tr[y].key)
				return tr[x].r=merge(tr[x].r,y),pushup(x),x;
			else return tr[y].l=merge(x,tr[y].l),pushup(y),y;
		}int build(ll val){int id=newid();return tr[id]={0,0,val,int(rnd()),1},id;}
		void insert(ll val){
			int x,y;split(rot,val,x,y);
			rot=merge(merge(x,build(val)),y);
		}void del(ll val){
			int x,y,z;split(rot,val,x,z);
			split(x,val-1,x,y);bin.pd(y);
			rot=merge(merge(x,merge(tr[y].l,tr[y].r)),z);
		}int Get_rank(int rt,int k){
			if(k<=tr[tr[rt].l].sz)return Get_rank(tr[rt].l,k);
			if(k==tr[tr[rt].l].sz+1)return rt;
			return Get_rank(tr[rt].r,k-tr[tr[rt].l].sz-1);
		}
		void clear(){for(int i=1;i<=cnt;i++)tr[i]={0,0,0,0,0};cnt=rot=0;bin.clear();}
	};
}
namespace segment_tree{
	const int N=2e5+10;
	template<typename M,typename T> struct sg_tree{
		struct node{M Mes;T Tag;int l,r;}tr[5];
		int rot;int cnt;
		void init(){for(int i=1;i<=cnt;i++)tr[i].Mes=M(),tr[i].Tag=T(),tr[i].l=tr[i].r=0;rot=cnt=0;}
		void pushup(int rt){
			tr[rt].Mes=M();
			if(tr[rt].l&&tr[rt].r)tr[rt].Mes=tr[tr[rt].l].Mes+tr[tr[rt].r].Mes;
			else if(tr[rt].l)tr[rt].Mes=tr[tr[rt].l].Mes;
			else if(tr[rt].r)tr[rt].Mes=tr[tr[rt].r].Mes;
		}
		void addson(int rt,T x){tr[rt].Mes=tr[rt].Mes+x;tr[rt].Tag=tr[rt].Tag+x;}
		void pushdown(int rt){
			if(tr[rt].Tag==T())return;
			if(tr[rt].l)addson(tr[rt].l,tr[rt].Tag);
			if(tr[rt].r)addson(tr[rt].r,tr[rt].Tag);
			tr[rt].Tag=T();
		}
		void build(int &rt,int l,int r,std::vector<M> &A){
			if(!rt)rt=++cnt;
			if(l==r)return tr[rt].Mes=A[l],void();
			auto mid=l+r>>1;
			build(tr[rt].l,l,mid,A);build(tr[rt].r,mid+1,r,A);
			pushup(rt);
		}
		void change_Seq(int &rt,int l,int r,int x,int y,T P){
			if(x>y)return;
			if(!rt)rt=++cnt,tr[rt].Mes=M(),tr[rt].Tag=T();
			if(x<=l&&r<=y)return addson(rt,P);
			auto mid=l+r>>1;pushdown(rt);
			if(x<=mid)change_Seq(tr[rt].l,l,mid,x,y,P);
			if(y>mid)change_Seq(tr[rt].r,mid+1,r,x,y,P);
			pushup(rt);
		}
		void change_p(int &rt,int l,int r,int x,T P){
			if(!rt)rt=++cnt,tr[rt].Mes=M(),tr[rt].Tag=T();
			if(l==r)return addson(rt,P);
			auto mid=l+r>>1;pushdown(rt);
			(x<=mid)?change_p(tr[rt].l,l,mid,x,P):change_p(tr[rt].r,mid+1,r,x,P);
			pushup(rt);
		}
		M query(int rt,int l,int r,int x,int y){
			if(!rt||x>y)return M();
			if(x<=l&&r<=y)return tr[rt].Mes;
			auto mid=l+r>>1;pushdown(rt);
			if(x<=mid&&y>mid)return query(tr[rt].l,l,mid,x,y)+query(tr[rt].r,mid+1,r,x,y);
			if(x<=mid)return query(tr[rt].l,l,mid,x,y);
			if(y>mid)return query(tr[rt].r,mid+1,r,x,y);
			assert(false);
		}
		void build(int l,int r,std::vector<M> &A){build(rot,l,r,A);}
		void change_Seq(int l,int r,int x,int y,T P){
			change_Seq(rot,l,r,x,y,P);}
		void change_p(int l,int r,int x,T P){
			change_p(rot,l,r,x,P);}
		M query(int l,int r,int x,int y){
			return query(rot,l,r,x,y);}
	};
	struct Mes{
		Mes(){}
		Mes(ll _S,int _l,int _r){}
		Mes operator + (Mes P){
			Mes ans=Mes();
			return ans;
		}
	};
	struct Tag{
		Tag(){}
		Tag operator + (Tag P){
			Tag ans=Tag();
			return ans;
		}
		bool operator == (Tag P){return true!=false;}
	};
	Mes operator + (Mes A,Tag B){return A;}
}
namespace Fenwick_Tree{
	const int N=2e5+10;
	struct FwT{
		ll tr[5];int u;
		void init(int _u){
			u=_u;
			for(int i=0;i<=u;i++)tr[i]=0;}
		void add(int x,ll y){for(;x<=u;x+=(x&-x))tr[x]+=y;}
		ll query(int x){ll ans=0;for(;x;x^=(x&-x))ans+=tr[x];return ans;}
		ll query(int l,int r){if(l>r)return 0;return query(r)-query(l-1);}
	};
}
//=========================================================
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll QA(ll x,ll y,ll mod){ll ans=0;for(;y;y>>=1,x=(x<<1)%mod)if(y&1)ans=(ans+x)%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
typedef unsigned U;
const int M=998244353;
struct ModInt{
	static constexpr U mod=M;
	U val;
	constexpr ModInt():val(0U){}
	constexpr ModInt(U _val):val(_val){}
	constexpr ModInt(int _val):val((_val%int(mod)+int(mod))%int(mod)){}
	constexpr ModInt(ll _val):val((_val%ll(mod)+ll(mod))%ll(mod)){}
	ModInt(const ModInt &P):val(P.val){}
	inline ModInt operator +(ModInt p){return ModInt(int(val)+int(p.val));}
	inline ModInt operator -(ModInt p){return ModInt(int(val)-int(p.val));}
	inline ModInt operator *(ModInt p){return ModInt(1ll*val*p.val);}
	inline ModInt QP(ll y){
		if(y<0)return inv().QP(-y);
		ModInt A=(*this),B=1U;
		for(;y;A=A*A,y>>=1)if(y&1)B=B*A;
		return B;
	}inline ModInt inv(){return QP(mod-2);}
	inline ModInt operator /(ModInt p){return (*this)*p.inv();}
	inline ModInt operator ^(ModInt p){return QP(p.val);}
	template<typename T>
	inline ModInt operator ^(T p){return QP(p);}

	template<typename T>
	inline ModInt operator +(T p){return (*this)+ModInt(p);}
	template<typename T>
	inline ModInt operator -(T p){return (*this)-ModInt(p);}
	template<typename T>
	inline ModInt operator *(T p){return (*this)*ModInt(p);}
	template<typename T>
	inline ModInt operator /(T p){return (*this)/ModInt(p);}

	inline ModInt operator +(){return (*this);}
	inline ModInt operator -(){return ModInt(0)-(*this);}

	template<typename T>
	inline friend ModInt operator +(T A,ModInt P){return ModInt(A)+P;}
	template<typename T>
	inline friend ModInt operator -(T A,ModInt P){return ModInt(A)-P;}
	template<typename T>
	inline friend ModInt operator *(T A,ModInt P){return ModInt(A)*P;}
	template<typename T>
	inline friend ModInt operator /(T A,ModInt P){return ModInt(A)/P;}

	inline void operator --(){val=(!val?mod-1:val-1);}
	inline void operator ++(){val=(val==mod-1?0:val+1);}

	inline void operator +=(ModInt P){(*this)=(*this)+P;}
	inline void operator -=(ModInt P){(*this)=(*this)-P;}
	inline void operator *=(ModInt P){(*this)=(*this)*P;}
	inline void operator /=(ModInt P){(*this)=(*this)/P;}

	template<typename T>
	inline void operator +=(T P){return (*this)=(*this)+ModInt(P);}
	template<typename T>
	inline void operator -=(T P){return (*this)=(*this)-ModInt(P);}
	template<typename T>
	inline void operator *=(T P){return (*this)=(*this)*ModInt(P);}
	template<typename T>
	inline void operator /=(T P){return (*this)=(*this)/ModInt(P);}
	template<typename T>
	inline void operator ^=(T P){return (*this)=(*this)^P;}

	U key(){return val;}
	inline bool operator == (ModInt P){return P.val==val;}
	inline bool operator != (ModInt P){return !((*this)==P);}

};
//=========================================================
namespace IO{
	const double eps=1e-8;
	const int BUFSIZE=1<<20;
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char tmp[BUFSIZE];int cnt=0;
	inline char getch(){if(is==it)it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);return is==it?EOF:*is++;}
	int readInt(){int x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	ll readLL(){ll x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	Int readInt128(){Int x=0;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	char readChar(){char c=0;while(!c||c==' '||c=='\n')c=getch();return c;}
	std::string readString(){std::string S;char c=0;while(!c||c==' '||c=='\n')c=getch();while(c!=' '&&c!='\n')S.pd(c),c=getch();return S;}
	LD readDouble(){LD x=0,d=1;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();int cnt=0;bool flg=false;while(isdigit(c)){
		x=x*10+(c^48),flg|=(c^48),cnt+=flg,c=getch();if(cnt>=12)goto flg;}if(c=='.'){c=getch();while(isdigit(c)){d*=10,x+=(c^48)/d;flg|=(c^48),cnt+=flg;
		if(cnt>=12)goto flg;c=getch();}}flg:;return !y?x:-x;}
	ul readUll(){ul x=0;char c=0;while(!isdigit(c))c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return x;}

	void flush(){fwrite(tmp,1,cnt,stdout);cnt=0;}
	void putch(char c){tmp[cnt++]=c;if(cnt==BUFSIZE)flush();}
	void putint(int x){char Q[10];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putInt128(Int x){char Q[45];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putLL(ll x){char Q[20];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putString(std::string x){for(auto p:x)putch(p);}
	void putDouble(LD x){if(x<0)x=-x,putch('-');if(fabs(x)<=eps)return putch(0);bool flg=false;LD d=1e10;LD l=std::min(LD(1e-10),1.0/std::max(LD(1),x));
		while(d>=l){if(d<=1){if(ll(x/d+d*1e-2)%10>0||flg)putch(ll(x/d+d*1e-2)%10+'0'),flg=true;}else{if(ll(x/d)%10>0||flg)putch(ll(x/d)%10+'0'),flg=true;
		}x-=ll(x/d+eps)*d; if(d==1){if(!flg)putch('0');putch('.');}d/=10;}}
	void putUll(ul x){char Q[25];int tp=0;if(!x)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}

	struct Basic{
		Basic &operator>>(int &A){A=IO::readInt();return (*this);}
		Basic &operator>>(ll &A){A=IO::readLL();return (*this);}
		Basic &operator>>(Int &A){A=IO::readInt128();return (*this);}
		Basic &operator>>(char &A){A=IO::readChar();return (*this);}
		Basic &operator>>(std::string &A){A=IO::readString();return (*this);}
		Basic &operator>>(double &A){A=IO::readDouble();return (*this);}
		Basic &operator>>(LD &A){A=IO::readDouble();return (*this);}
		Basic &operator>>(float &A){A=IO::readDouble();return (*this);}
		template<typename T1,typename T2>
		Basic &operator>>(std::pair<T1,T2>&v){(*this)>>v.first>>v.second;return (*this);}
		template<typename T,int d>
		Basic &operator>>(std::array<T,d> &v){for(auto &p:v)(*this)>>p;return (*this);}
		template<typename T>
		Basic &operator>>(std::vector<T> &v){for(auto &p:v)(*this)>>p;return (*this);}
		Basic &operator>>(ul &v){v=readUll();return (*this);}

		Basic &operator<<(const int &A){putint(A);return (*this);}
		Basic &operator<<(const char &A){putch(A);return (*this);}
		Basic &operator<<(const ll &A){putLL(A);return (*this);}
		Basic &operator<<(const Int &A){putInt128(A);return (*this);}
		Basic &operator<<(const std::string &A){putString(A);return (*this);}
		Basic &operator<<(const LD &A){putDouble(A);return (*this);}
		Basic &operator<<(const double &A){putDouble(A);return (*this);}
		Basic &operator<<(const float &A){putDouble(A);return (*this);}
		template<typename T>
		Basic &operator<<(const std::vector<T> &v){for(int i=0;i<v.size();i++)(*this)<<v[i]<<(v.size()==i+1?'\n':' ');return (*this);}
		Basic &operator<<(const ul &A){putUll(A);return (*this);}

		void Flush(){flush();}
	}cin,cout;
}
//=========================================================
namespace Grader{
	std::vector<int>S;
	void Get(std::vector<int>v){
		assert(S.empty());

		reverse(all(S));
	}
	int readInt(){
		assert(!S.empty());
		int x=S.back();
		S.pop_back();
		return x;
	}
	void putInt(int x){
		std::vector<int>P;
		P.pd(x);Get(P);
	}void putVec(std::vector<int>v){Get(v);}
}
//=========================================================
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
//=========================================================
//const int mod=998244353;
//int add(int x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;return x;}
//int mul(int x,int y){return 1ll*x*y%mod;}
//void add(int &x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;}
const int N=2e5+10;
const int C1[2][4]={{1,1,2,2},{1,2,1,2}};
const int C2[3][3]={{0,1,1},{2,2,1},{2,1,2}};
const int C3[3][4]={{1,1,0,0},{1,2,1,2},{0,0,2,2}};
void Sub1(){
	IO::cout<<0<<'\n';
	IO::cout<<0<<'\n';
}
void Sub2(){
	IO::cout<<2<<'\n';
	IO::cout<<"0 1 1\n2 2 1\n2 1 2\n";
}
void Sub3(){
	IO::cout<<5<<'\n';
	IO::cout<<"0 1 1 2 2\n3 3 1 4 2\n3 1 3 2 4\n5 5 0 4 4\n5 0 5 0 0\n";
}
void Sub4(){
	IO::cout<<11<<'\n';
	IO::cout<<"0 1 1 2 2 3 3\n4 4 1 5 2 6 3\n4 1 4 5 2 6 3\n7 7 0 5 5 6 6\n7 0 7 0 0 8 8\n9 9 10 10 11 11 8\n9 10 9 10 11 8 11\n";
}
void Sub5(int n,ve<ve<int>>&v){
	int cnt=0;
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=n;j+=4){
			for(int S1=i;S1<=i+1;S1++)
				for(int S2=j;S2<=j+3;S2++)
					v[S1][S2]=C1[S1-i][S2-j]+cnt;
			cnt+=2;
		}
	}
	IO::cout<<cnt<<'\n';
}
void Sub6(int n,ve<ve<int>>&v){
	int cnt=0;
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=n-2;j+=4){
			for(int S1=i;S1<=i+1;S1++)
				for(int S2=j;S2<=j+3;S2++)
					v[S1][S2]=C1[S1-i][S2-j]+cnt;
			cnt+=2;
		}
	}
	for(int i=1;i<=n-2;i+=4){
		for(int S1=n-1;S1<=n;S1++)
			for(int S2=i;S2<=i+3;S2++)
				v[S2][S1]=C1[S1-(n-1)][S2-i]+cnt;
		cnt+=2;
	}
	IO::cout<<cnt<<'\n';
}
void copy(ve<ve<int>>&v,int x1,int y1,int opt,int r,int cnt){
	ve<ve<int>>S;
	if(opt==1){
		if(r&1^1){
			for(int i=0;i<2;i++){
				S.pd({});
				for(int j=0;j<4;j++)
					S.back().pd(C1[i][j]);
			}
		}else{
			for(int i=0;i<4;i++){
				S.pd({});
				for(int j=0;j<2;j++)
					S.back().pd(C1[j][i]);
			}
		}
	}if(opt==2){
		S=ve<ve<int>>(3,ve<int>(3));
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++)
				S[i][j]=C2[i][j];
		while(r--){
			auto P=S;
			for(int i=0;i<3;i++)
				for(int j=0;j<3;j++)
					S[j][2-i]=P[i][j];
		}
	}if(opt==3){
		if(r%4==0){
			S=ve<ve<int>>(3,ve<int>(4));
			for(int i=0;i<3;i++)
				for(int j=0;j<4;j++)
					S[i][j]=C3[i][j];
		}if(r%4==1){
			S=ve<ve<int>>(4,ve<int>(3));
			for(int i=0;i<3;i++)
				for(int j=0;j<4;j++)
					S[j][i]=C3[i][j];
		}if(r%4==2){
			S=ve<ve<int>>(3,ve<int>(4));
			for(int i=0;i<3;i++)
				for(int j=0;j<4;j++)
					S[2-i][j]=C3[i][j];
		}if(r%4==3){
			S=ve<ve<int>>(4,ve<int>(3));
			for(int i=0;i<3;i++)
				for(int j=0;j<4;j++)
					S[j][i]=C3[i][j];
		}
	}for(int i=x1;i<=x1+S.size()-1;i++)
		for(int j=y1;j<=y1+S[0].size()-1;j++)
			if(S[i-x1][j-y1]){
				if(v[i][j]){
					for(auto &p:S)IO::cout<<p;IO::cout.Flush(); 
					exit(0);
				}assert(!v[i][j]),v[i][j]=S[i-x1][j-y1]+cnt;
			}
				
}
void Sub7(int n,ve<ve<int>>&v){
	int cnt=0;
	auto get=[&](int x1,int y1,int x2,int y2,auto self)->void{
		if(x2-x1+1==9){
			copy(v,x1,y1,1,0,cnt);cnt+=2;
			copy(v,x1,y1+4,2,3,cnt);cnt+=2;
			copy(v,x1,y1+7,1,1,cnt);cnt+=2;
			copy(v,x1+2,y1,2,2,cnt);cnt+=2;
			copy(v,x1+2,y1+3,3,0,cnt);cnt+=2;
			copy(v,x1+4,y1+2,3,0,cnt);cnt+=2;
			copy(v,x1+5,y1,1,1,cnt);cnt+=2;
			copy(v,x1+6,y1+2,2,1,cnt);cnt+=2;
			copy(v,x1+7,y1+5,1,0,cnt);cnt+=2;
			copy(v,x1+4,y1+6,2,0,cnt);cnt+=2;
			return;
		};
		int L=x2-x1+1;
		if(L%4==3){
			self(x1,y1,x2-2,y2-2,self);
			for(int i=x1;i<=x2-3;i+=4)
				copy(v,i,y2-1,1,1,cnt),cnt+=2;
			for(int i=y1;i<=y2-3;i+=4)
				copy(v,x2-1,i,1,0,cnt),cnt+=2;
			copy(v,x2-2,y2-2,2,0,cnt),cnt+=2;
		}else{
			self(x1+2,y1,x2-2,y2-4,self);
			for(int i=y1;i<=y2-5;i+=4)
				copy(v,x1,i,1,0,cnt),cnt+=2,
				copy(v,x2-1,i,1,0,cnt),cnt+=2;
			copy(v,x1,y2-4,3,3,cnt),cnt+=2;
			copy(v,x1,y2-2,2,3,cnt),cnt+=2;
			copy(v,x2-2,y2-4,2,0,cnt),cnt+=2;
			copy(v,x2-3,y2-1,1,1,cnt),cnt+=2;
			copy(v,x2-5,y2-3,3,2,cnt),cnt+=2;
			for(int i=x1+4;!v[i][y2-3];i+=4){
				copy(v,i,y2-3,1,1,cnt),cnt+=2;
				copy(v,i-1,y2-1,1,1,cnt),cnt+=2;
			}
		}
	};
	get(1,1,n,n,get);
	IO::cout<<cnt<<'\n';
}
void solve(){
	//don't forget to open long long
	int n;IO::cin>>n;
	ve<ve<int>>v(n+1,ve<int>(n+1));
	auto write=[&]()->void{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				IO::cout<<v[i][j]<<char(j==n?'\n':' ');
	}; 
	if(n==1)Sub1();
	else if(n==3)Sub2();
	else if(n==5)Sub3(); 
	else if(n==7)Sub4();
	else if(n%4==0)Sub5(n,v),write();
	else if(n%4==2)Sub6(n,v),write();
	else Sub7(n,v),write();
	
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	//std::ios::sync_with_stdio(false);
	//std::cin.tie(0);
	//std::cout.tie(0);
	int T=1;IO::cin>>T; 
	while(T--)solve();

	IO::cout.Flush();
	return 0;
}