#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int q, n;
char ch, cur;

int main() {
    fin >> q;
    while (q > 0) {
        stack<char> st;
        bool can = true;
        fin >> n;
        if (n == 1) {
            n = 0;
            fin >> ch;
        } else if (n == 2) {
            can = false;
            n = 0;
            fin >> ch >> ch;
        } else {
            fin >> ch;
            //cout << "Citim " << ch << endl;
            if (ch == '1') {
                if (n == 3) {
                    fin >> ch;
                    if (ch != '2')
                        can = false;
                    fin >> ch;
                    //cout << "#" << ch;
                    st.push('3');
                    n = 0;
                } else {
                    st.push('C');
                    st.push('A');
                    st.push('3');
                    st.push('A');
                    st.push('1');
                }
            } else if (ch == '2') {
                st.push('B');
                st.push('2');
            } else if (ch == '3') {
                st.push('C');
                st.push('B');
                st.push('3');
            }
            n--;
            //cout << "Punem " << ch << endl;
            //cout << "Distrugem " << st.top() << endl;
            st.pop();
        }
        while (n > 0 && can) {
            //cout << st.size();
            fin >> ch;
            //cout << "Citim " << ch << endl;
            cur = st.top();
            //cout << "Avem in varf " << cur << endl;
            if (cur != ch) {
                if (cur >= '1' && cur <= '3') {
                    can = false;
                } else {
                    if (cur == 'A') {
                        //cout << "Punem " << ch << endl;
                        /// nu facem nimic
                    } else if (cur == 'B') {
                        if (ch == '1') {
                            //cout << "Punem " << ch << endl;
                            st.pop();
                            st.push('C');
                            st.push('A');
                            st.push('3');
                            st.push('A');
                            st.push('1');
                            //cout << "Push B2" << endl;
                        } else if (ch == '2') {
                            //cout << "Punem " << ch << endl;
                            st.pop();
                            st.push('B');
                            st.push('2');
                            //cout << "Push B1" << endl;
                        } else if (ch == '3') {
                            can = false;
                            st.push('3');
                            //cout << "Avem B si nu putem pune 3!!!!" << endl;
                        }
                    } else if (cur == 'C') {
                        if (ch == '1') {
                            //cout << "Punem " << ch << endl;
                            st.pop();
                            st.push('A');
                            st.push('2');
                            st.push('1');
                            //cout << "Distrugem C" << endl;
                            //cout << "Push C3" << endl;
                        } else if (ch == '2') {
                            //cout << "Punem " << ch << endl;
                            st.pop();
                            st.push('2');
                            //cout << "Push C1" << endl;
                        } else if (ch == '3') {
                            //cout << "Punem " << ch << endl;
                            st.pop();
                            st.push('C');
                            st.push('B');
                            st.push('3');
                            //cout << "Push C2" << endl;
                        }
                    }
                }
            }
            //cout << endl;
            //cout << "Distrugem " << st.top() << endl;
            st.pop();
            n--;
        }
        while (n > 0) {
            fin >> ch;
            n--;
            can = false;
        }
        //cout << 1;
        if (!st.empty())
            can = false;

        if (can)
            fout << "1\n";
        else
            fout << "0\n";
        //cout << endl;
        //cout << endl;
        q--;
    }
    return 0;
}