#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stack>
#define cout g
#define inf 1<<30
#define lmax 10005
using namespace std;

int n;
string target, temp;
bool posibil;


int rezolva(string s) {
	if(s.size() > target.size() || posibil) return 0;
	if(s.size() == target.size()) {
		posibil = true;
		for(int i=0; i<s.size() && posibil; i++) if(s[i]!=target[i]) posibil = false;
	}
	
	if(posibil) return 0;
	
	//cout<<s<<"\n";
		
	for(int i = 0; i < s.size(); i++) {
		if(s[i] == 'A') {
			rezolva( s.substr(0, i) + '1' + s.substr(i+1, s.npos) );
			rezolva( s.substr(0, i) + '2' + s.substr(i+1, s.npos) );
			rezolva( s.substr(0, i) + '3' + s.substr(i+1, s.npos) );
		}
		if(s[i] == 'B') {
			rezolva( s.substr(0, i) + "2B" + s.substr(i+1, s.npos) );
			rezolva( s.substr(0, i) + "1A3AC" + s.substr(i+1, s.npos) );
		}
		if(s[i] == 'C') {
			rezolva( s.substr(0, i) + '2' + s.substr(i+1, s.npos) );
			rezolva( s.substr(0, i) + "3BC" + s.substr(i+1, s.npos) );
			rezolva( s.substr(0, i) + "12A" + s.substr(i+1, s.npos) );
		}
		
	}
	return 0;
}

int main() {
	ifstream f("perle.in");
	ofstream g("perle.out");

	f>>n;
	f.get();
	while(n--) {
		getline(f,temp);
		target = "";
		for(int i=1; i<temp.size(); i++)
			if(temp[i] != ' ') target += temp[i];
		//cout<<"<"<<target<<">";
		posibil = false;

		rezolva("A");
		if(!posibil) rezolva("B");
		if(!posibil) rezolva("C");
		cout<<posibil<<"\n";
	}

	return 0;
}