#include <iostream>
#include <fstream>
#include <iostream>

using namespace std;

char st[10002];

int N, nr, perl, vf;

int main(){

    ifstream f("perle.in");
    ofstream g("perle.out");

    f >> N;

    for(int i = 1; i <= N; i++){

        f >> nr;
        vf = 0;

        if(nr == 1){

            g << "1\n";
            f >> perl;
        }

        else{
                f >> perl;

                if(perl == 3)
                    st[++vf] = 'C';
                else
                    if(perl == 2)
                        st[++vf] = 'B';
                    else
                        if(perl == 1 && nr == 3)
                            st[++vf] = 'C';
                        else
                            st[++vf] = 'B';

                bool OK = true;

                for(int j = 1; j <= nr; j++){

                    if(OK){

                        if(st[vf] == 'A')
                            st[vf] = perl + 48;
                        else
                            if(st[vf] == 'B')
                                if(perl == 2)
                                    st[++vf] = '2';
                                else
                                    if(perl == 1)
                                        st[vf] = 'C',
                                        st[++vf] = 'A',
                                        st[++vf] = '3',
                                        st[++vf] = 'A',
                                        st[++vf] = '1';
                                    else
                                        OK = false;
                            else
                                if(st[vf] == 'C')
                                    if(perl == 2)
                                        st[vf] = '2';
                                    else
                                        if(perl == 3)
                                            st[++vf] = 'B',
                                            st[++vf] = '3';
                                        else
                                            if(perl == 1)
                                                st[vf] = 'A',
                                                st[++vf] = '2',
                                                st[++vf] = '1';

                        if(OK && st[vf] - 48 == perl)
                            vf--;
                        else
                            OK = false;
                    }

                    if(j < nr)
                        f >> perl;
                }

                if(OK && vf == 0)
                    g << "1\n";
                else
                    g << "0\n";

                }
    }

    return 0;
}