#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;
const ll inf = 1e18;

using vl = vector<ll>;

vector<vector<vector<int>>> parts[5];

ll xorVl(vl &vals) {
	if (vals.size() == 0) return inf;
	ll a = 0;
	for (ll i : vals) a^= i;
	return a;
}

vl arr;
struct Ans {
	ll a = inf, b = inf;
	vl l, r;
	bool operator<(const Ans &rhs) const {
		return min(a,b) < min(rhs.a, rhs.b);
	}
};
Ans solve(vl vals, int bit=31) {
	if (vals.size() == 0) {
		return {inf, inf, {}, {} };
	}
	if (vals.size() == 1) {
		return {inf, inf, vals, {} };
	}
	if (vals.size() == 2) {
		return {inf, inf, {vals[0]}, {vals[1]}};
	}
	if (bit == -1) {
		for (int i = 1; i < vals.size(); i++) assert(arr[vals[i]] == arr[vals[0]]);
		vals.pop_back();
		return { 0, inf, vals, {vals[0]} };
	}
	vl l, r;
	for (ll i : vals) {
		if (arr[i]&(1<<bit)) r.push_back(i);
		else l.push_back(i);
	}

	if (r.size() == 1) {
		if (l.size() == 0) {
			Ans a = { inf, inf, { r[0] }, { } };
			return a;
		}
		if (l.size() == 1) {
			Ans a = { arr[l[0]] ^ arr[r[0]], inf, { l[0], r[0] }, { l[1] } };
			Ans b = { arr[l[1]] ^ arr[r[0]], inf, { l[1], r[0] }, { l[0] } };
			return max(a,b);
		}
		else if (l.size() == 2) {
			Ans a = { arr[l[0]] ^ arr[r[0]], inf, { l[0], r[0] }, { l[1] } };
			Ans b = { arr[l[1]] ^ arr[r[0]], inf, { l[1], r[0] }, { l[0] } };
			return max(a,b);
		}
	}

	if (r.size() == 2) {
		if (l.size() == 0) {
			Ans a = { inf, inf, { r[0] }, { r[1] } };
			return a;
		}
		if (l.size() == 1) {
			Ans a = { arr[l[0]] ^ arr[r[0]], inf, { l[0], r[0] }, { r[1] } };
			Ans b = { arr[l[0]] ^ arr[r[1]], inf, { l[0], r[1] }, { r[0] } };
			return max(a,b);
		}
		else if (l.size() == 2) {
			Ans a = { arr[l[0]] ^ arr[r[0]], arr[l[1]] ^ arr[r[1]], { l[0], r[0] }, { l[1], r[1] } };
			Ans b = { arr[l[0]] ^ arr[r[1]], arr[l[1]] ^ arr[r[0]], { l[0], r[1] }, { l[1], r[0] } };
			return max(a,b);
		}
	}

	Ans x = solve(l, bit-1), y = solve(r, bit-1);
	Ans out = { min(x.a, y.a), min(x.b, y.b), {}, {} };
	while (x.l.size()) {
		out.l.push_back(x.l.back());
		x.l.pop_back();
	}
	while (y.l.size()) {
		out.l.push_back(y.l.back());
		y.l.pop_back();
	}

	while (x.r.size()) {
		out.r.push_back(x.r.back());
		x.r.pop_back();
	}
	while (y.r.size()) {
		out.r.push_back(y.r.back());
		y.r.pop_back();
	}
	return out;
}

void solve() {
	int n; cin >> n;
	arr.resize(n);
	for (ll &i : arr) cin >> i;
	vl idxs(n);
	for (int i = 0; i < n; i++) idxs[i] = i;
	Ans out = solve(idxs);
	cout << min(out.a, out.b) << endl;
	vector<int> col(n, 1);
	for (int i : out.l) col[i] = 2;
	for (int i : col) cout << 2 - (i == col[0]);
	cout << endl;
}

int main() {
	int t; cin >> t;
	while (t--) solve();
}