#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 11, MAXL = 10001;

int L[MAXN + 1], N;
bool ok[MAXN + 1];

vector <string> sequences(MAXN + 1);

void citire()
{
    scanf("%d",&N);

    for(int i = 1; i <= N; i++)
    {
        scanf("%d",&L[ i ]);

        for(int j = 1; j <= 2*L[ i ]; j++)
        {
            char c;
            scanf("%c",&c);

            if( c != ' ' && c != '\n' )
                sequences[ i ] += c;
        }
    }
}

string target;
int lim, index;

void back(string left, string mid, string right)
{
    string s; s += left; s += mid; s += right;

    //cout<<s<<endl;

    if( s == target )
        ok[ index ] = true;

    if( s.length() <= lim )
    {

        if( s == target )
            return;

        int i = 0;

        while( target[ i ] == s[ i ] )
            i++;

        for( ; i < s.length(); i++)
        {
            int r = s.length() - i - 1;

            if( s[ i ] == 'A' )
            {
                string c; c += target[ i ];

                back( s.substr(0,i), c, s.substr(i+1,r) );
            }
            else
            if( s[ i ] == 'B' )
            {
                if( target[ i ] == '2' )
                    back( s.substr(0,i), "2B", s.substr(i+1,r) );

                if( target[ i ] == '1' )
                    back( s.substr(0,i), "1A3AC", s.substr(i+1,r) );
            }
            else
            if( s[ i ] == 'C' )
            {
                if( target[ i ] == '1' )
                    back( s.substr(0,i), "12A", s.substr(i+1,r) );

                if( target[ i ] == '2' )
                    back( s.substr(0,i), "2", s.substr(i+1,r) );

                if( target[ i ] == '3' )
                    back( s.substr(0,i), "3BC", s.substr(i+1,r) );
            }
        }

        //cout<<endl;

    }
    else return;
}


void solve()
{
    for(int i = 1; i <= N; i++)
    {
        target = sequences[ i ];
        index = i;
        lim = target.length();

        string a, b;

        back(a,"A",b);

        if( ok[ index ] == false )
            back(a,"B",b);

        if( ok[ index ] == false )
            back(a,"C",b);
    }
}

void print()
{
    for(int i = 1; i <= N; i++)
        printf("%d\n",ok[ i ]);
}


int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);

    citire();
    solve();
    print();
    return 0;
}