#include <bits/stdc++.h>

using namespace std;

stack <char> st;

void solve()
{
    int L;
    cin >> L;
    vector <char> v(L + 1);

    while(!st.empty())
        st.pop();

    for(int i = 1; i <= L; i ++)
    {
        cin >> v[i];
    }

    if(L == 1)
    {
        cout << "1\n";
        return;
    }
    if(L == 2)
    {
        cout << "0\n";
        return;
    }
    if(L == 3)
    {
        if(v[1] == '1'  &&  v[2] == '2')
            cout << "1\n";
        else
            cout << "0\n";
        return;
    }
    if(v[1] == '1'  ||  v[1] == '2')
        st.push('b');
    else
        st.push('c');

    int i = 1, ok = 1;
    while(!st.empty()  &&  i <= L  &&  ok)
    {
        if(isdigit(st.top()))
        {
            if(st.top() == v[i])
            {
                st.pop();
                i ++;
            }
            else
                ok = 0;
            continue;
        }

        int curr = st.top();
        st.pop();

        if(curr == 'b')
        {
            if(v[i] == '2')
            {
                //"2B"
                st.push('b');
//                cout << "b - 2b\n";
                i ++;
            }
            else if(v[i] == '1')
            {
                //"1A3AC"
                st.push('c');
                st.push('a');
                st.push('3');
                st.push('a');
//                cout << "b - 1a3ac\n";
                i ++;
            }
            else
                ok = 0;
        }
        else if (curr == 'c')
        {
            if(v[i] == '1')
            {
                //"12A"
                st.push('a');
                st.push('2');
//                cout << "c - 12a\n";
                i ++;
            }
            else if(v[i] == '2')
            {
                i ++;
//                cout << "c - 2\n";
            }
            else if(v[i] == '3')
            {
                //"3BC"
                st.push('c');
                st.push('b');
                i ++;
//                cout << "c - 3bc\n";
            }
        }
        else
        {
            i ++;
//            cout << "a\n";
        }
    }

    if(i == L + 1  &&  st.empty()  &&  ok == 1)
        cout << "1\n";
    else
        cout << "0\n";
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

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

    int n;
    cin >> n;
    while(n)
    {
        n --;
        solve();
    }

    return 0;
}