#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
*/

bool solve(string s, int n)
{
    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");
            }
        }
        //cout << s << " " << i << "\n";

        if (s[i] != v[i] || s.size() > n)
        {
            return 0;
            break;
        }
    }
    if (s.size() == n)
        return 1;
    return 0;
}

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 (solve("C", n) || solve("B" ,n))
            fout << 1 << " \n";
        else
            fout << 0 << "\n";
    }

    return 0;
}