#include <stack>
#include <iostream>
#include <fstream>
using namespace std;

void print_st(stack<char> st){
	while(!st.empty()){
		cout << st.top();
	 	st.pop(); } }

bool verifica(ifstream& f){
	int nr_perle = 0;
	f >> nr_perle;
	if(nr_perle == 1){
		int vreau_sa_ma_scap_de_perla = 0;
		f >> vreau_sa_ma_scap_de_perla;
		return true; }
	else{
		char nou;
		stack<char> posibilitati[2];
		posibilitati[0].push('B');
		posibilitati[1].push('C');
		bool e_posibil[2] = {true, true};
		for(int i = 0; i < nr_perle; ++i){
			f.ignore();
			nou = f.get();
			for(int j = 0; j < 2; ++j){
				if(posibilitati[j].empty()){
					e_posibil[j] = false; }
				else if(e_posibil[j]){
					switch(posibilitati[j].top()){
					default:
						if(posibilitati[j].top() == nou){
							posibilitati[j].pop(); }
						else{
							e_posibil[j] = false; }
						break;
					case 'A':
						posibilitati[j].pop();
						break;
					case 'B':
						switch(nou){
						case '1':
							posibilitati[j].pop();
							posibilitati[j].push('C');
							posibilitati[j].push('A');
							posibilitati[j].push('3');
							posibilitati[j].push('A'); 
							break;
						case '3':
							e_posibil[j] = false;
							break; }
						break;
					case 'C':
						switch(nou){
						case '1':
							posibilitati[j].pop();
							posibilitati[j].push('A');
							posibilitati[j].push('2');
							break;
						case '2':
							posibilitati[j].pop();
							break;
						case '3':
							posibilitati[j].push('B');
							break; }
						break; } } } }
		for(int i = 0; i < 2; ++i){
			cout << e_posibil[i] << '*';
			print_st(posibilitati[i]);
			cout << '\n'; }
		cout << '\n';
		return (e_posibil[0] && posibilitati[0].empty()) ||
			(e_posibil[1] && posibilitati[0].empty()); } }

int main(){
	ifstream f("perle.in");
	ofstream g("perle.out");
	int n = 0;
	f >> n;
	for(int i = 0; i < n; ++i){
		g << verifica(f) << '\n'; }
	return 0; }