1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define fi first
  5. #define se second
  6. const int N=2001;
  7. // -------------------- Input Checker Start --------------------
  8.  
  9. long long readInt(long long l, long long r, char endd)
  10. {
  11.     long long x = 0;
  12.     int cnt = 0, fi = -1;
  13.     bool is_neg = false;
  14.     while(true)
  15.     {
  16.         char g = getchar();
  17.         if(g == '-')
  18.         {
  19.             assert(fi == -1);
  20.             is_neg = true;
  21.             continue;
  22.         }
  23.         if('0' <= g && g <= '9')
  24.         {
  25.             x *= 10;
  26.             x += g - '0';
  27.             if(cnt == 0)
  28.                 fi = g - '0';
  29.             cnt++;
  30.             assert(fi != 0 || cnt == 1);
  31.             assert(fi != 0 || is_neg == false);
  32.             assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
  33.         }
  34.         else if(g == endd)
  35.         {
  36.             if(is_neg)
  37.                 x = -x;
  38.             if(!(l <= x && x <= r))
  39.             {
  40.                 cerr << l << ' ' << r << ' ' << x << '\n';
  41.                 assert(false);
  42.             }
  43.             return x;
  44.         }
  45.         else
  46.         {
  47.             assert(false);
  48.         }
  49.     }
  50. }
  51.  
  52. string readString(int l, int r, char endd)
  53. {
  54.     string ret = "";
  55.     int cnt = 0;
  56.     while(true)
  57.     {
  58.         char g = getchar();
  59.         assert(g != -1);
  60.         if(g == endd)
  61.             break;
  62.         cnt++;
  63.         ret += g;
  64.     }
  65.     assert(l <= cnt && cnt <= r);
  66.     return ret;
  67. }
  68.  
  69. long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
  70. long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
  71. string readStringLn(int l, int r) { return readString(l, r, '\n'); }
  72. string readStringSp(int l, int r) { return readString(l, r, ' '); }
  73. void readEOF() { assert(getchar() == EOF); }
  74.  
  75. vector<int> readVectorInt(int n, long long l, long long r)
  76. {
  77.     vector<int> a(n);
  78.     for(int i = 0; i < n - 1; i++)
  79.         a[i] = readIntSp(l, r);
  80.     a[n - 1] = readIntLn(l, r);
  81.     return a;
  82. }
  83.  
  84. // -------------------- Input Checker End --------------------
  85. int n;
  86. int a[N],b[N],d[N];
  87. pair<int,int>c[N];
  88. void _kill(int id,int bit){
  89. 	b[id]|=(1<<(bit+1))-1;
  90. 	b[id]^=(1<<bit);
  91. }
  92. int god[N];
  93. int lg[N];
  94. int e[N][N];
  95. void add(int x,int y){
  96. 	e[x][y]=e[y][x]=1;
  97. }
  98. void out(){
  99. 	for(int i=1; i<=n ;i++){
  100. 		for(int j=1; j<=n ;j++){
  101. 			cout << e[i][j];
  102. 		}
  103. 		cout << '\n';
  104. 	}
  105. }
  106. bool check(){
  107. 	int x=0;
  108. 	for(int i=1; i<=n ;i++) x^=b[i];
  109. 	return (x==0);
  110. }
  111. void treesolve(stack<int>&st, int star){
  112. 	for(int i=star; i>=1 ;i--){
  113. 		int x=st.top();
  114. 		while(d[x]==b[x]){
  115. 			st.pop();x=st.top();
  116. 		}
  117. 		d[x]++;d[c[i].se]++;
  118. 		add(x,c[i].se);
  119. 		st.push(c[i].se);
  120. 	}
  121. }
  122. int tot=1e7;
  123. void solve(){
  124. 	n=readInt(1,2000,'\n');
  125. 	tot-=n*n;
  126. 	assert(tot>=0);
  127. 	for(int i=1; i<=n ;i++){
  128. 		for(int j=1; j<=n ;j++){
  129. 			e[i][j]=0;
  130. 		}
  131. 		d[i]=b[i]=0;
  132. 	}
  133. 	int funny=0;
  134. 	int ss=0;
  135. 	int c1=0;
  136. 	for(int i=1; i<=n ;i++){
  137. 		if(i==n) a[i]=readInt(1,n,'\n');
  138. 		else a[i]=readInt(1,n-1,' ');
  139. 		c[i]={a[i],i};
  140. 		funny^=a[i];
  141. 		ss+=a[i];
  142. 		c1+=(a[i]==1);
  143. 	}
  144. 	if(ss<2*n-2 || n==3){//not enough edges
  145. 		cout << "NO\n";
  146. 		return;
  147. 	}
  148. 	if(c1>=n-1){
  149. 		if(n==2) cout << "YES\n01\n10\n";
  150. 		else cout << "NO\n";
  151. 		return;
  152. 	}
  153. 	sort(c+1,c+n+1);
  154. 	if(c[1].fi>=2 && n%2==0){
  155. 		cout << "YES\n";
  156. 		for(int i=1; i<n ;i++) add(i,i+1);
  157. 		add(1,n);
  158. 		out();return;
  159. 	}
  160. 	if(c[n-1].fi*2>n && c[n].fi*2>n+1 && n%4!=1){
  161. 		if(n%2==0){
  162. 			cout << "YES\n";
  163. 			for(int i=1; i<=n/2-1 ;i++) add(c[i].se,c[n-1].se);
  164. 			for(int i=n/2; i<=n-2 ;i++) add(c[i].se,c[n].se);
  165. 			add(c[n-1].se,c[n].se);
  166. 			out();return;
  167. 		}
  168. 		if(n%8==3){
  169. 			if(c[n-2].fi==1){
  170. 				cout << "NO\n";return;
  171. 			}
  172. 			cout << "YES\n";
  173. 			for(int i=1; i<=n/2 ;i++) add(c[i].se,c[n].se);
  174. 			for(int i=n/2+1; i<=n-3 ;i++) add(c[i].se,c[n-1].se);
  175. 			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);
  176. 			out();return;
  177. 		}
  178. 		if(c[n-3].fi!=1){
  179. 			for(int i=1; i<=n-4 ;i++) b[c[i].se]=1;
  180. 			b[c[n-3].se]=b[c[n-2].se]=2;
  181. 			b[c[n-1].se]=n/2-1;b[c[n].se]=n/2;
  182. 			stack<int>st;st.push(c[n].se);
  183. 			treesolve(st,n-1);
  184. 			cout << "YES\n";
  185. 			out();return;
  186. 		}
  187. 		for(int i=2; i<=c[n-2].fi ;i++){
  188. 			for(int j=2; j<=c[n-1].fi ;j++){
  189. 				{
  190. 					int k=2*n-2-i-j-(n-3);
  191. 					if(k>1 && k<=c[n].fi && (i^j^k)==0){
  192. 						for(int i=1; i<=n-3 ;i++) b[c[i].se]=1;
  193. 						b[c[n-2].se]=i;b[c[n-1].se]=j;b[c[n].se]=k;
  194. 						stack<int>st;st.push(c[n].se);
  195. 						treesolve(st,n-1);	
  196. 						cout << "YES\n";
  197. 						out();return;
  198. 					}
  199. 				}
  200. 				{
  201. 					int k=2*n-i-j-(n-3);
  202. 					if(k>1 && k<=c[n].fi && (i^j^k)==0){
  203. 						for(int i=1; i<=n-3 ;i++) b[c[i].se]=1;
  204. 						b[c[n-2].se]=i;b[c[n-1].se]=j;b[c[n].se]=k;
  205. 						stack<int>st;
  206. 						d[c[n].se]+=2;d[c[n-1].se]+=2;d[c[n-2].se]+=2;
  207. 						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);
  208. 						st.push(c[n].se);st.push(c[n-1].se);st.push(c[n-2].se);
  209. 						treesolve(st,n-3);
  210. 						cout << "YES\n";
  211. 						out();return;
  212. 					}
  213. 				}
  214. 			}
  215. 		}
  216. 		cout << "NO\n";
  217. 		return;
  218. 		//n%4==1 doesnt exhibit this bad behavior
  219. 	}
  220. 	if(funny==0){
  221. 		for(int i=1; i<=n ;i++) b[i]=a[i];
  222. 	}
  223. 	else{
  224. 		bool ok=false;
  225. 		if(funny==1){
  226. 			for(int i=1; i<=n ;i++){
  227. 				if(a[i]%2==1 && a[i]>=3){
  228. 					for(int j=1; j<=n ;j++) b[j]=a[j];
  229. 					b[i]--;
  230. 					ok=true;
  231. 					break;//s is guarenteed to be >=2*n-2, and sum b is maximized 
  232. 				}
  233. 			}
  234. 		}
  235. 		if(!ok){//now carrying must happen
  236. 			int en=1;
  237. 			for(int i=10; i>=en ;i--){
  238. 				vector<pair<pair<int,int>,int> >v;
  239. 				int mk=(1<<(i+1))-1;
  240. 				for(int j=1; j<=n ;j++){
  241. 					int cur=a[j]&mk;
  242. 					if((cur>>i)&1) v.push_back({{cur,-a[j]},j});
  243. 				}
  244. 				if(v.empty()) continue;//nothing to carry, cannot try
  245. 				sort(v.begin(),v.end());
  246. 				for(int j=1; j<=n ;j++) b[j]=a[j];
  247. 				int spc=v[0].se;
  248. 				if(v.size()%2==1){//1 or 3 carrying happens
  249. 					en=i;//carrying must happen
  250. 					bool fucked=true;
  251. 					for(int j=1; j<=n ;j++) fucked&=(a[j]==(1<<i)) || (a[j]==1);//i hope correct :P
  252. 					if(fucked && funny%2==0){//last resort is to use 3, if still fail then die
  253. 						_kill(v[0].se,i);_kill(v[1].se,i);_kill(v[2].se,i);
  254. 					}
  255. 					else{
  256. 						_kill(v[0].se,i);//remove i-th bit from v[0]
  257. 					}
  258. 				}
  259. 				else{//two carrying happens (4 cant help impossible->possible)
  260. 					_kill(v[0].se,i);_kill(v[1].se,i);
  261. 				}/*
  262. 				for(int j=1; j<=n ;j++) cout << b[j] << ' ';
  263. 				cout << endl;*/
  264. 				//i~10th bit works now
  265. 				//greedy to maximize sum b
  266. 				//spc stores some 2^k-1
  267. 				for(int k=i-1; k>=1 ;k--){//fix 1~i-1 bit
  268. 					int cnt=0;
  269. 					int mn=spc;
  270. 					for(int j=1; j<=n ;j++){
  271. 						if((b[j]>>k)&1){
  272. 							cnt++;
  273. 							int cv=b[j]&((1<<k)-1);
  274. 							int mv=b[mn]&((1<<k)-1);
  275. 							if(cv<mv) mn=j;
  276. 						}
  277. 					}
  278. 					if(cnt%2==1){//odd number of k-th bit, sacrifice min dude
  279. 						_kill(mn,k);
  280. 					}
  281. 				}
  282. 				{///fix last bit
  283. 					int orz=0;
  284. 					for(int j=1; j<=n ;j++) orz^=b[j];
  285. 					if(orz%2==1){
  286. 						bool done=false;
  287. 						for(int j=1; j<=n ;j++){
  288. 							if(b[j]%2==1 && b[j]>=3){
  289. 								b[j]--;done=true;break;
  290. 							}
  291. 						}
  292. 						if(!done) continue;
  293. 					}
  294. 				}
  295. 				
  296. 				int sum=0;
  297. 				for(int j=1; j<=n ;j++) sum+=b[j];
  298. 				if(sum>=2*n-2){
  299. 					ok=true;break;
  300. 				}
  301. 			}
  302. 			if(!ok){
  303. 				cout << "NO\n";
  304. 				return;
  305. 			}
  306. 		}
  307. 	}
  308. 	//current: b xor to 0, 1<=b[i]<=a[i], sum b>=2n-2
  309. 	//aim: sum b<=2n
  310. 	
  311. 	/*
  312. 	for(int i=1; i<=n ;i++) cout << b[i] << ' ';
  313. 	cout << endl;*/
  314. 	for(int i=0; i<=10 ;i++) god[i]=0;
  315. 	int sum=0;
  316. 	stack<int>s;
  317. 	if(!check()) while(true);
  318. 	for(int i=1; i<=n ;i++){
  319. 		sum+=b[i];
  320. 		s.push(i);
  321. 	}
  322. 	while(!s.empty() && sum>2*n){
  323. 		int x=s.top();s.pop();
  324. 		if(b[x]==1) continue;
  325. 		int y=b[x]&-b[x];
  326. 		int z=lg[y];
  327. 		if(god[z]!=0){
  328. 			int w=god[z];
  329. 			int frog=min((sum-(2*n-2))/2,1<<z);
  330. 			if(b[w]==(1<<z) || b[x]==(1<<z)) frog=min(frog,(1<<z)-1);
  331. 			b[w]-=frog;b[x]-=frog;sum-=2*frog;
  332. 			god[z]=0;
  333. 			s.push(w);s.push(x);
  334. 			//either both minbit + (>=1) or at least 1 die, another reset
  335. 		}
  336. 		else god[z]=x;
  337. 	}
  338. 	
  339. 	if(!check()) while(true);
  340. 	/*
  341. 	for(int i=1; i<=n ;i++) cout << b[i] << ' ';
  342. 	cout << endl;*/
  343. 	//now sum is O(nlogn)
  344. 	vector<int>vip;
  345. 	for(int i=1; i<=n ;i++) if(b[i]!=1) vip.push_back(i);
  346. 	while(sum>2*n){//each iteration sum -2 at least
  347. 		for(int i=0; i<=10 ;i++) god[i]=0;
  348. 		while(!s.empty()) s.pop();
  349. 		for(auto x:vip) s.push(x);
  350. 		while(!s.empty() && sum>2*n){
  351. 			int x=s.top();s.pop();
  352. 			if(b[x]==1) continue;
  353. 			int y=b[x]&-b[x];
  354. 			int z=lg[y];
  355. 			if(god[z]!=0){
  356. 				int w=god[z];
  357. 				int frog=min((sum-(2*n-2))/2,1<<z);
  358. 				if(b[w]==(1<<z) || b[x]==(1<<z)) frog=min(frog,(1<<z)-1);
  359. 				b[w]-=frog;b[x]-=frog;sum-=2*frog;
  360. 				god[z]=0;
  361. 				s.push(w);s.push(x);
  362. 				//either both minbit + (>=1) or at least 1 die, another reset
  363. 			}
  364. 			else god[z]=x;
  365. 		}
  366. 		if(sum<=2*n) break;
  367. 		for(int j=1; j<=10 ;j++){//cannot do nothing inside here
  368. 			if(god[j]!=0 && god[0]!=0){
  369. 				int w=god[0];
  370. 				int x=god[j];
  371. 				if(b[x]!=2){
  372. 					int frog=2;
  373. 					b[w]-=frog;b[x]-=frog;sum-=2*frog;
  374. 				}
  375. 				else{
  376. 					b[w]-=3;b[x]-=1;sum-=4;
  377. 				}
  378. 				break;
  379. 			}
  380. 		}
  381. 	}
  382. 	
  383. 	if(!check()) while(true);
  384. 	//now sum in [2n-2,2n]
  385. 	
  386. 	/*
  387. 	for(int i=1; i<=n ;i++) cout << b[i] << ' ';
  388. 	cout << endl;*/
  389. 	for(int i=1; i<=n ;i++) c[i]={b[i],i};
  390. 	sort(c+1,c+n+1);
  391. 	stack<int>st;
  392. 	if(sum==2*n-2){
  393. 		st.push(c[n].se);
  394. 		treesolve(st,n-1);
  395. 	}
  396. 	else{
  397. 		d[c[n].se]+=2;d[c[n-1].se]+=2;d[c[n-2].se]+=2;
  398. 		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);
  399. 		st.push(c[n].se);st.push(c[n-1].se);st.push(c[n-2].se);
  400. 		treesolve(st,n-3);
  401. 	}
  402. 	cout << "YES\n";
  403. 	out();return;
  404. }
  405. int main(){
  406. 	ios::sync_with_stdio(false);cin.tie(0);
  407. 	for(int i=0; i<=10 ;i++) lg[1<<i]=i;
  408. 	int t;t=readInt(1,10000,'\n');while(t--){solve();/*cout << endl;*/}readEOF();
  409. }