#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("perle.in");
ofstream fout ("perle.out");
int t, n;
char v[10005];
string s;

int main() {
    fin >> t;
    while (t--) {
        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 magic = true;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == 'A')
                s[i] = v[i];
            else if (s[i] == 'B') {
                s.erase(i);
                if (v[i] == '2')
                    s.insert(i, "2B");
                else if (v[i] == '1')
                    s.insert(i, "1A3AC");;
            }
            else if (s[i] == 'C') {
                s.erase(i);
                if (v[i] == '2')
                    s.insert(i, "2");
                else if (v[i] == '3')
                    s.insert(i, "3BC");
                else if (v[i] == '1')
                    s.insert(i, "12A");
            }
            if (s[i] != v[i] || s.size() > n) {
                magic = false;
                break;
            }
        }
        if (magic)
            fout << 1 << "\n";
        else
            fout << 0 << "\n";
        /*for (int i = 0; i < s.size(); ++i)
            cout << s[i] << " ";
        cout << "\n";*/
    }
    return 0;
}