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

ifstream cin("perle.in");
ofstream cout("perle.out");

string b1 = "2B";
string b2 = "1A3AC";

string c1 ="2";
string c2 = "3BC";
string c3 = "12A";
stack<string> st;

void solve()
{
    while (!st.empty())
        st.pop();
    int n ;
    cin >> n ;
    string tg ;
    tg.clear();
    string bg ;
    bg.clear();
    for ( int i = 1 ; i <= n ; i ++ )
    {
        char a ;
        cin >> a ;
        tg .push_back(a);
    }

    if ( n == 1 )
    {
        cout << 1 << '\n';
        return ;
    }

    if ( tg [ 0 ] == '2')
    {
        bg.push_back('B');
    }
    else if ( tg [ 0 ] == '3')
        bg.push_back('C');
    else if ( tg [ 0 ] == '1')
    {
        if ( n == 3 )
        {
            bg.push_back('C');
        }
        else
            bg.push_back('B');
    }

    for ( int i = 0 ; i < n ; i ++ )
    {


        for ( int j = bg.size() - 1 ; j > i ; j --  )
        {
            string  a;
            a += bg [ j ] ;


            st.push(a);
             a.clear() ;
        }


        while ( bg.size() > i + 1)
            bg.pop_back();


        if ( bg [ i ] == 'A')
            bg [ i ] = tg [ i ] ;

        if ( bg [ i ] == 'B')
        {

            if ( tg [ i ] == '1')
            {
                bg.pop_back();
                bg += b2;

            }
            else if ( tg [ i ] == '2' )
            {
                bg.pop_back();
                bg += b1 ;

            }
            else
            {
                cout << 0 << '\n';
                return ;
            }


        }
        else
        {
            if ( bg [ i ] == 'C')
            {

                if ( tg [ i ] == '2' )
                {

                    bg [i ] = '2';

                }
                else if ( tg [ i ] == '3' )
                {
                    bg.pop_back();
                    bg += c2;
                }
                else
                {
                    bg.pop_back();
                    bg += c3 ;
                }
            }

        }

        while (!st.empty())
        {
            string a ;
            a = st.top();
            bg += a;
            a.clear();
            st.pop();
        }

    }

    if ( bg.size() != tg.size())
    {

        cout << 0 << '\n';
        return ;
    }

    for ( int i = 0; i < n ; i ++ )
    {
        if ( tg [ i ] != bg [ i ])
        {
            cout << 0 << '\n';
            return ;
        }
    }

    cout << 1 << '\n';
}
int main()
{
    int test ;
    cin >> test ;
    while ( test--)
        solve();

    return 0;
}