1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. vector<int> solve_degseq(vector<int> D) {
  8. 	int N = D.size();
  9. 	if(N == 2) return {1,1};
  10. 	if(N == 3 || D[3] == 1) {
  11. 		// bruteforce
  12. 		vector<int> d(N, 1);
  13. 		for(d[0] = 1; d[0] <= D[0]; d[0]++) for(d[1] = 1; d[1] <= D[1]; d[1]++) {
  14. 			d[2] = d[0]^d[1]^(1^N&1);
  15. 			if(d[2] > D[2]) continue;
  16. 			if(d[0] < d[1] || d[1] < d[2] || d[2] == 0) continue;
  17. 			if(d[0]+d[1] > 2+min(2,d[2])+(N-3)) continue;
  18. 			if(d[0]+d[1]+d[2] > 6+(N-3)) continue;
  19. 			if(d[0]+d[1]+d[2]+(N-3) < 2*(N-1)) continue;
  20. 			return d;
  21. 		}
  22. 		return {};
  23. 	}
  24. 	// init. sequence
  25. 	int D_sum = 0;
  26. 	for(int i = 0; i < N; i++) D_sum += D[i];
  27. 	vector<int> d_init(N);
  28. 	if(D_sum >= 5*N+4) {
  29. 		for(int i = 0; i < N; i++) {
  30. 			d_init[i] = 1;
  31. 			while(2*d_init[i] <= D[i]) d_init[i] *= 2;
  32. 		}
  33. 		int x = 0;
  34. 		for(int i = 0; i < N; i++) x ^= d_init[i];
  35. 		for(int b = 16; b >= 1; b--) if((x>>b)&1) {
  36. 			for(int i = N-1; i >= 0; i--) if(d_init[i] == (1<<b)) {
  37. 				x ^= (1<<b)^(1<<(b-1));
  38. 				d_init[i] = 1<<(b-1);
  39. 				break;
  40. 			}
  41. 		}
  42. 		if(x) {
  43. 			for(int i = 0; i < N; i++) if(d_init[i]%2 == 0 && d_init[i] < D[i]) {
  44. 				d_init[i]++;
  45. 				x = 0;
  46. 				break;
  47. 			}
  48. 		}
  49. 		if(x) {
  50. 			for(int i = N-1; i > 0; i--) if(d_init[i] == d_init[0]) {
  51. 				d_init[i] -= 2;
  52. 				d_init[i-1]--;
  53. 				x = 0;
  54. 				break;
  55. 			}
  56. 		}
  57. 	}
  58. 	else {
  59. 		vector< vector<int> > max_d_sum(N+1, vector<int>(2*N, -4*N));
  60. 		max_d_sum[0][0] = 0;
  61. 		for(int i = 0; i < N; i++)
  62. 			for(int x = 0; x < 2*N; x++) if(max_d_sum[i][x] >= 0)
  63. 				for(int j = 1; j <= D[i]; j++)
  64. 					max_d_sum[i+1][x^j] = max(max_d_sum[i+1][x^j], max_d_sum[i][x]+j);
  65. 		if(max_d_sum[N][0] < 2*(N-1)) return {};
  66. 		int x = 0, s = max_d_sum[N][0];
  67. 		for(int i = N-1; i >= 0; i--) {
  68. 			for(int j = 1; j <= min(s,D[i]); j++) if(max_d_sum[i][x^j] == s-j) {
  69. 				s -= j;
  70. 				x ^= j;
  71. 				d_init[i] = j;
  72. 				break;
  73. 			}
  74. 		}
  75. 		sort(rbegin(d_init), rend(d_init));
  76. 	}
  77. 	// valid sequence
  78. 	vector<int> lsb(N);
  79. 	for(int i = 1; i < N; i++) {
  80. 		lsb[i] = 0;
  81. 		while((i&(1<<lsb[i])) == 0) lsb[i]++;
  82. 	}
  83. 	vector<int> d = d_init;
  84. 	int B = 0;
  85. 	while((2<<B) < N) B++;
  86. 	vector< vector<int> > id_by_lsb(B+1);
  87. 	for(int i = 0; i < N; i++) if(d[i] > 1) id_by_lsb[lsb[d[i]]].push_back(i);
  88. 	int d_sum = 0;
  89. 	for(int i = 0; i < N; i++) d_sum += d[i];
  90. 	while(d_sum > 2*(N-1)) {
  91. 		int b = -1;
  92. 		for(int i = 0; i <= B; i++) if((int)id_by_lsb[i].size() >= 2) {
  93. 			b = i;
  94. 			break;
  95. 		}
  96. 		bool sub1 = (b == -1 && d_sum > 2*N);
  97. 		if(sub1) {
  98. 			int id0 = id_by_lsb[0].back();
  99. 			id_by_lsb[0].pop_back();
  100. 			d[id0]--;
  101. 			id_by_lsb[lsb[d[id0]]].push_back(id0);
  102. 			for(int i = 0; i <= B; i++) if((int)id_by_lsb[i].size() >= 2) {
  103. 				b = i;
  104. 				break;
  105. 			}
  106. 		}
  107. 		if(b == -1) break;
  108. 		int id1 = id_by_lsb[b].back();
  109. 		id_by_lsb[b].pop_back();
  110. 		int id2 = id_by_lsb[b].back();
  111. 		id_by_lsb[b].pop_back();
  112. 		int s = sub1 ? 1 : min(d_sum/2-N+1, min(1<<b, min(d[id1],d[id2])-1));
  113. 		d[id1] -= s, d[id2] -= s;
  114. 		if(d[id1] > 1) id_by_lsb[lsb[d[id1]]].push_back(id1);
  115. 		if(d[id2] > 1) id_by_lsb[lsb[d[id2]]].push_back(id2);
  116. 		if(sub1) {
  117. 			int id0 = id_by_lsb[0].back();
  118. 			id_by_lsb[0].pop_back();
  119. 			d[id0]--;
  120. 			id_by_lsb[lsb[d[id0]]].push_back(id0);
  121. 			d_sum -= 2+2*s;
  122. 		}
  123. 		else d_sum -= 2*s;
  124. 	}
  125. 	sort(rbegin(d), rend(d));
  126. 	if(d[2] == 1 && d_sum == 2*N) d[2] = d[3] = 2;
  127. 	return d;
  128. }
  129.  
  130. vector< vector<int> > construct(vector<int> d) {
  131. 	int N = d.size();
  132. 	vector< pair<int,int> > ds(N);
  133. 	for(int i = 0; i < N; i++) ds[i] = {d[i], i};
  134. 	vector< vector<int> > G(N);
  135. 	for(int i = 0; i < N-1; i++) {
  136. 		for(int j = 1; j <= ds[0].first; j++) {
  137. 			G[ds[0].second].push_back(ds[j].second);
  138. 			G[ds[j].second].push_back(ds[0].second);
  139. 			ds[j].first--;
  140. 		}
  141. 		vector< pair<int,int> > ds_nw(N-1-i);
  142. 		merge(rbegin(ds), rbegin(ds)+(N-1-i-ds[0].first), rbegin(ds)+(N-1-i-ds[0].first), rend(ds)-1, rbegin(ds_nw));
  143. 		ds = ds_nw;
  144. 	}
  145. 	return G;
  146. }
  147.  
  148. void DFS(int v, int v_prev, vector< vector<int> > & G, vector<char> & vis, pair<int, int> & e) {
  149. 	for(auto v_nxt : G[v]) if(v_nxt != v_prev) {
  150. 		if(vis[v_nxt]) {
  151. 			if(e.first == -1) e = {v, v_prev};
  152. 			break;
  153. 		}
  154. 		vis[v_nxt] = 1;
  155. 		DFS(v_nxt, v, G, vis, e);
  156. 	}
  157. }
  158.  
  159. pair<int,int> find_edge_on_cycle(vector< vector<int> > & G, int v_init) {
  160. 	int N = G.size();
  161. 	vector<char> vis(N, 0);
  162. 	pair<int, int> e = {-1,-1};
  163. 	vis[v_init] = 1;
  164. 	DFS(v_init, v_init, G, vis, e);
  165. 	return e;
  166. }
  167.  
  168. vector< vector<int> > make_connected(vector< vector<int> > G) {
  169. 	int N = G.size();
  170. 	vector<int> in_comp(N, -1), edges;
  171. 	vector< vector<int> > comp;
  172. 	int C = 0;
  173. 	for(int i = 0; i < N; i++) if(in_comp[i] == -1) {
  174. 		in_comp[i] = C;
  175. 		comp.push_back({i});
  176. 		edges.push_back(0);
  177. 		static queue<int> q;
  178. 		q.push(i);
  179. 		while(!q.empty()) {
  180. 			for(auto v : G[q.front()]) if(in_comp[v] == -1) {
  181. 				in_comp[v] = C;
  182. 				comp.back().push_back(v);
  183. 				q.push(v);
  184. 			}
  185. 			q.pop();
  186. 		}
  187. 		for(auto v : comp.back()) edges.back() += G[v].size();
  188. 		C++;
  189. 	}
  190. 	while(C > 1) {
  191. 		pair<int,int> e1, e2;
  192. 		int c1 = 0;
  193. 		if(edges.back()+2 == 2*(int)comp.back().size()) {
  194. 			while(edges[c1]+2 == 2*(int)comp[c1].size()) c1++;
  195. 			e2 = {comp.back()[0], G[comp.back()[0]].back()};
  196. 			e1 = find_edge_on_cycle(G, comp[c1][0]);
  197. 		}
  198. 		else {
  199. 			e2 = find_edge_on_cycle(G, comp.back()[0]);
  200. 			e1 = {comp[c1][0], G[comp[c1][0]].back()};
  201. 		}
  202. 		replace(begin(G[e1.first]), end(G[e1.first]), e1.second, e2.second);
  203. 		replace(begin(G[e1.second]), end(G[e1.second]), e1.first, e2.first);
  204. 		replace(begin(G[e2.first]), end(G[e2.first]), e2.second, e1.second);
  205. 		replace(begin(G[e2.second]), end(G[e2.second]), e2.first, e1.first);
  206. 		for(auto v : comp.back()) in_comp[v] = c1;
  207. 		comp[c1].insert(end(comp[c1]), begin(comp.back()), end(comp.back()));
  208. 		edges[c1] += edges.back();
  209. 		comp.pop_back();
  210. 		edges.pop_back();
  211. 		C--;
  212. 	}
  213. 	return G;
  214. }
  215.  
  216. int main() {
  217. 	cin.sync_with_stdio(0);
  218. 	cin.tie(0);
  219. 	int T;
  220. 	cin >> T;
  221. 	while(T--) {
  222. 		int N;
  223. 		cin >> N;
  224. 		vector<int> D(N);
  225. 		for(int i = 0; i < N; i++) cin >> D[i];
  226. 		vector< pair<int,int> > Ds(N);
  227. 		for(int i = 0; i < N; i++) Ds[i] = {D[i], i};
  228. 		sort(rbegin(Ds), rend(Ds));
  229. 		vector<int> id(N);
  230. 		for(int i = 0; i < N; i++) id[Ds[i].second] = i;
  231. 		for(int i = 0; i < N; i++) D[i] = Ds[i].first;
  232. 		auto d = solve_degseq(D);
  233. 		if(d.empty()) {
  234. 			cout << "NO\n";
  235. 			continue;
  236. 		}
  237. 		cout << "YES\n";
  238. 		auto G = construct(d);
  239. 		auto G_conn = make_connected(G);
  240. 		for(int i = 0; i < N; i++) {
  241. 			string s(N, '0');
  242. 			for(auto v : G_conn[id[i]]) s[Ds[v].second] = '1';
  243. 			cout << s << "\n";
  244. 		}
  245. 	}
  246. }