#include <bits/stdc++.h>
using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");

enum type {
	A, B, C
};

#define BUFSIZE (1 << 16)
char buf[BUFSIZE];

bool rec(char *s, int len, type t) {
	if (t == A)
		return (len == 1);
	
	if (t == B) {
		int pos = 0;
		while (s[pos] == '2')
			++pos;
		
		if (pos)
			return rec(s + pos, len - pos, B);

		if (s[0] != '1' || s[2] != '3')
			return false;

		return rec(s + 4, len - 4, C);
	}

	if (len == 1)
		return s[0] == '2';
	if (len == 3)
		return s[0] == '1' && s[1] == '2';

	if (s[0] != '3')
		return false;

	int pos = 1;
	while (s[pos] == '2')
		++pos;

	if (s[0] != '1' || s[2] != '3')
		return false;

	return rec(s + 4, len - 4, C);
}

void solve() {
	int l;
	fin >> l;

	for (int i = 0; i < l; ++i)
		fin >> buf[i];

	buf[l] = '\0';

	cout << buf << '\n';

	fout << (rec(buf, l, A) || rec(buf, l, B) || rec(buf, l, C)) << '\n';
}

int main() {
	int n;
	fin >> n;

	while (n--)
		solve();
}