#include <bits/stdc++.h>

using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");

const int lmax = 10007;
char v[lmax];
string s;

/*
    A -> 1 | 2 | 3
    B -> 2B | 1A3AC
    C -> 2 | 3BC | 12A
*/

int main()
{
    int t;
    fin >> t;

    while (t--)
    {
        int n;
        fin >> n;

        for (int i = 0; i < n; i++)
        {
            fin >> v[i];
        }

        if (n == 1)
        {
            fout << "1\n";
            continue;
        }

        if(n == 3)
        {
            if(v[0] == '1' && v[1] == '2')
                fout << "1\n";
            else
                fout << "0\n";
            continue;
        }

        s.clear();
        if (v[0] == '1')
        {
            s += "1A3AC";
        }
        else if (v[0] == '2')
        {
            s += "2B";
        }
        else
        {
            s += "3BC";
        }

        bool ok = 1;

        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == 'A')
            {
                s[i] = v[i];
            }
            else if (s[i] == 'B')
            {
                s.erase(i, 1);
                if (v[i] == '1')
                {
                    s.insert(i, "1A3AC");
                }
                else if (v[i] == '2')
                {
                    s.insert(i, "2B");
                }
            }
            else if (s[i] == 'C')
            {
                s.erase(i, 1);
                if (v[i] == '1')
                {
                    s.insert(i, "12A");
                }
                else if (v[i] = '2')
                {
                    s.insert(i, "2");
                }
                else if (v[i] == '3')
                {
                    s.insert(i, "3BC");
                }
            }
            if (s[i] != v[i] || s.size() > n)
            {
                ok = 0;
                break;
            }
            
        }

        if (ok)
            fout << 1 << "\n";
        else
            fout << 0 << "\n";
    }

    return 0;
}