#include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second const int N=2001; // -------------------- Input Checker Start -------------------- long long readInt(long long l, long long r, char endd) { long long x = 0; int cnt = 0, fi = -1; bool is_neg = false; while(true) { char g = getchar(); if(g == '-') { assert(fi == -1); is_neg = true; continue; } if('0' <= g && g <= '9') { x *= 10; x += g - '0'; if(cnt == 0) fi = g - '0'; cnt++; assert(fi != 0 || cnt == 1); assert(fi != 0 || is_neg == false); assert(!(cnt > 19 || (cnt == 19 && fi > 1))); } else if(g == endd) { if(is_neg) x = -x; if(!(l <= x && x <= r)) { cerr << l << ' ' << r << ' ' << x << '\n'; assert(false); } return x; } else { assert(false); } } } string readString(int l, int r, char endd) { string ret = ""; int cnt = 0; while(true) { char g = getchar(); assert(g != -1); if(g == endd) break; cnt++; ret += g; } assert(l <= cnt && cnt <= r); return ret; } long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); } long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); } string readStringLn(int l, int r) { return readString(l, r, '\n'); } string readStringSp(int l, int r) { return readString(l, r, ' '); } void readEOF() { assert(getchar() == EOF); } vector<int> readVectorInt(int n, long long l, long long r) { vector<int> a(n); for(int i = 0; i < n - 1; i++) a[i] = readIntSp(l, r); a[n - 1] = readIntLn(l, r); return a; } // -------------------- Input Checker End -------------------- int n; int a[N],b[N],d[N]; pair<int,int>c[N]; void _kill(int id,int bit){ b[id]|=(1<<(bit+1))-1; b[id]^=(1<<bit); } int god[N]; int lg[N]; int e[N][N]; void add(int x,int y){ e[x][y]=e[y][x]=1; } void out(){ for(int i=1; i<=n ;i++){ for(int j=1; j<=n ;j++){ cout << e[i][j]; } cout << '\n'; } } bool check(){ int x=0; for(int i=1; i<=n ;i++) x^=b[i]; return (x==0); } void treesolve(stack<int>&st, int star){ for(int i=star; i>=1 ;i--){ int x=st.top(); while(d[x]==b[x]){ st.pop();x=st.top(); } d[x]++;d[c[i].se]++; add(x,c[i].se); st.push(c[i].se); } } int tot=1e7; void solve(){ n=readInt(1,2000,'\n'); tot-=n*n; assert(tot>=0); for(int i=1; i<=n ;i++){ for(int j=1; j<=n ;j++){ e[i][j]=0; } d[i]=b[i]=0; } int funny=0; int ss=0; int c1=0; for(int i=1; i<=n ;i++){ if(i==n) a[i]=readInt(1,n,'\n'); else a[i]=readInt(1,n-1,' '); c[i]={a[i],i}; funny^=a[i]; ss+=a[i]; c1+=(a[i]==1); } if(ss<2*n-2 || n==3){//not enough edges cout << "NO\n"; return; } if(c1>=n-1){ if(n==2) cout << "YES\n01\n10\n"; else cout << "NO\n"; return; } sort(c+1,c+n+1); if(c[1].fi>=2 && n%2==0){ cout << "YES\n"; for(int i=1; i<n ;i++) add(i,i+1); add(1,n); out();return; } if(c[n-1].fi*2>n && c[n].fi*2>n+1 && n%4!=1){ if(n%2==0){ cout << "YES\n"; for(int i=1; i<=n/2-1 ;i++) add(c[i].se,c[n-1].se); for(int i=n/2; i<=n-2 ;i++) add(c[i].se,c[n].se); add(c[n-1].se,c[n].se); out();return; } if(n%8==3){ if(c[n-2].fi==1){ cout << "NO\n";return; } cout << "YES\n"; for(int i=1; i<=n/2 ;i++) add(c[i].se,c[n].se); for(int i=n/2+1; i<=n-3 ;i++) add(c[i].se,c[n-1].se); add(c[n-2].se,c[n-1].se);add(c[n-2].se,c[n].se);add(c[n-1].se,c[n].se); out();return; } if(c[n-3].fi!=1){ for(int i=1; i<=n-4 ;i++) b[c[i].se]=1; b[c[n-3].se]=b[c[n-2].se]=2; b[c[n-1].se]=n/2-1;b[c[n].se]=n/2; stack<int>st;st.push(c[n].se); treesolve(st,n-1); cout << "YES\n"; out();return; } for(int i=2; i<=c[n-2].fi ;i++){ for(int j=2; j<=c[n-1].fi ;j++){ { int k=2*n-2-i-j-(n-3); if(k>1 && k<=c[n].fi && (i^j^k)==0){ for(int i=1; i<=n-3 ;i++) b[c[i].se]=1; b[c[n-2].se]=i;b[c[n-1].se]=j;b[c[n].se]=k; stack<int>st;st.push(c[n].se); treesolve(st,n-1); cout << "YES\n"; out();return; } } { int k=2*n-i-j-(n-3); if(k>1 && k<=c[n].fi && (i^j^k)==0){ for(int i=1; i<=n-3 ;i++) b[c[i].se]=1; b[c[n-2].se]=i;b[c[n-1].se]=j;b[c[n].se]=k; stack<int>st; d[c[n].se]+=2;d[c[n-1].se]+=2;d[c[n-2].se]+=2; add(c[n].se,c[n-1].se);add(c[n].se,c[n-2].se);add(c[n-1].se,c[n-2].se); st.push(c[n].se);st.push(c[n-1].se);st.push(c[n-2].se); treesolve(st,n-3); cout << "YES\n"; out();return; } } } } cout << "NO\n"; return; //n%4==1 doesnt exhibit this bad behavior } if(funny==0){ for(int i=1; i<=n ;i++) b[i]=a[i]; } else{ bool ok=false; if(funny==1){ for(int i=1; i<=n ;i++){ if(a[i]%2==1 && a[i]>=3){ for(int j=1; j<=n ;j++) b[j]=a[j]; b[i]--; ok=true; break;//s is guarenteed to be >=2*n-2, and sum b is maximized } } } if(!ok){//now carrying must happen int en=1; for(int i=10; i>=en ;i--){ vector<pair<pair<int,int>,int> >v; int mk=(1<<(i+1))-1; for(int j=1; j<=n ;j++){ int cur=a[j]&mk; if((cur>>i)&1) v.push_back({{cur,-a[j]},j}); } if(v.empty()) continue;//nothing to carry, cannot try sort(v.begin(),v.end()); for(int j=1; j<=n ;j++) b[j]=a[j]; int spc=v[0].se; if(v.size()%2==1){//1 or 3 carrying happens en=i;//carrying must happen bool fucked=true; for(int j=1; j<=n ;j++) fucked&=(a[j]==(1<<i)) || (a[j]==1);//i hope correct :P if(fucked && funny%2==0){//last resort is to use 3, if still fail then die _kill(v[0].se,i);_kill(v[1].se,i);_kill(v[2].se,i); } else{ _kill(v[0].se,i);//remove i-th bit from v[0] } } else{//two carrying happens (4 cant help impossible->possible) _kill(v[0].se,i);_kill(v[1].se,i); }/* for(int j=1; j<=n ;j++) cout << b[j] << ' '; cout << endl;*/ //i~10th bit works now //greedy to maximize sum b //spc stores some 2^k-1 for(int k=i-1; k>=1 ;k--){//fix 1~i-1 bit int cnt=0; int mn=spc; for(int j=1; j<=n ;j++){ if((b[j]>>k)&1){ cnt++; int cv=b[j]&((1<<k)-1); int mv=b[mn]&((1<<k)-1); if(cv<mv) mn=j; } } if(cnt%2==1){//odd number of k-th bit, sacrifice min dude _kill(mn,k); } } {///fix last bit int orz=0; for(int j=1; j<=n ;j++) orz^=b[j]; if(orz%2==1){ bool done=false; for(int j=1; j<=n ;j++){ if(b[j]%2==1 && b[j]>=3){ b[j]--;done=true;break; } } if(!done) continue; } } int sum=0; for(int j=1; j<=n ;j++) sum+=b[j]; if(sum>=2*n-2){ ok=true;break; } } if(!ok){ cout << "NO\n"; return; } } } //current: b xor to 0, 1<=b[i]<=a[i], sum b>=2n-2 //aim: sum b<=2n /* for(int i=1; i<=n ;i++) cout << b[i] << ' '; cout << endl;*/ for(int i=0; i<=10 ;i++) god[i]=0; int sum=0; stack<int>s; if(!check()) while(true); for(int i=1; i<=n ;i++){ sum+=b[i]; s.push(i); } while(!s.empty() && sum>2*n){ int x=s.top();s.pop(); if(b[x]==1) continue; int y=b[x]&-b[x]; int z=lg[y]; if(god[z]!=0){ int w=god[z]; int frog=min((sum-(2*n-2))/2,1<<z); if(b[w]==(1<<z) || b[x]==(1<<z)) frog=min(frog,(1<<z)-1); b[w]-=frog;b[x]-=frog;sum-=2*frog; god[z]=0; s.push(w);s.push(x); //either both minbit + (>=1) or at least 1 die, another reset } else god[z]=x; } if(!check()) while(true); /* for(int i=1; i<=n ;i++) cout << b[i] << ' '; cout << endl;*/ //now sum is O(nlogn) vector<int>vip; for(int i=1; i<=n ;i++) if(b[i]!=1) vip.push_back(i); while(sum>2*n){//each iteration sum -2 at least for(int i=0; i<=10 ;i++) god[i]=0; while(!s.empty()) s.pop(); for(auto x:vip) s.push(x); while(!s.empty() && sum>2*n){ int x=s.top();s.pop(); if(b[x]==1) continue; int y=b[x]&-b[x]; int z=lg[y]; if(god[z]!=0){ int w=god[z]; int frog=min((sum-(2*n-2))/2,1<<z); if(b[w]==(1<<z) || b[x]==(1<<z)) frog=min(frog,(1<<z)-1); b[w]-=frog;b[x]-=frog;sum-=2*frog; god[z]=0; s.push(w);s.push(x); //either both minbit + (>=1) or at least 1 die, another reset } else god[z]=x; } if(sum<=2*n) break; for(int j=1; j<=10 ;j++){//cannot do nothing inside here if(god[j]!=0 && god[0]!=0){ int w=god[0]; int x=god[j]; if(b[x]!=2){ int frog=2; b[w]-=frog;b[x]-=frog;sum-=2*frog; } else{ b[w]-=3;b[x]-=1;sum-=4; } break; } } } if(!check()) while(true); //now sum in [2n-2,2n] /* for(int i=1; i<=n ;i++) cout << b[i] << ' '; cout << endl;*/ for(int i=1; i<=n ;i++) c[i]={b[i],i}; sort(c+1,c+n+1); stack<int>st; if(sum==2*n-2){ st.push(c[n].se); treesolve(st,n-1); } else{ d[c[n].se]+=2;d[c[n-1].se]+=2;d[c[n-2].se]+=2; add(c[n].se,c[n-1].se);add(c[n].se,c[n-2].se);add(c[n-1].se,c[n-2].se); st.push(c[n].se);st.push(c[n-1].se);st.push(c[n-2].se); treesolve(st,n-3); } cout << "YES\n"; out();return; } int main(){ ios::sync_with_stdio(false);cin.tie(0); for(int i=0; i<=10 ;i++) lg[1<<i]=i; int t;t=readInt(1,10000,'\n');while(t--){solve();/*cout << endl;*/}readEOF(); }