#include <fstream>
#include <stack>
using namespace std;

FILE *f=fopen("perle.in","r");
ofstream g("perle.out");

int main()
{
    int cs;

    fscanf(f,"%d",&cs);

    while(cs--){
        int n;
        fscanf(f,"%d",&n);

        int v[10001];
        for(int i=1;i<=n;i++)
            fscanf(f,"%d",&v[i]);

        if(n==1){
            g<<1<<'\n';
            continue;
        }
        if(n==3&&v[1]==1&&v[2]==2){
            g<<1<<'\n';
            continue;
        }
        stack<char> cr;
        int i=2;

        if(v[1]==2)
            cr.push('B');
        if(v[1]==1){
            cr.push('C'); cr.push('A'); cr.push('3'); cr.push('A');
        }
        if(v[1]==3){
            cr.push('C');cr.push('B');
        }

        while(i<=n){
            switch(cr.top()){
                case '1': case '2': case '3':
                    if(v[i]!=cr.top()-'0'){
                        g<<0<<'\n';
                        goto stop;
                    }
                    i++;
                    cr.pop();
                    break;

                case 'A':
                    i++;
                    cr.pop();
                    break;

                case 'B':
                    if(v[i]==3){
                        g<<0<<'\n';
                        goto stop;
                    }
                    cr.pop();
                    if(v[i]==1){
                        cr.push('C'); cr.push('A'); cr.push('3'); cr.push('A');
                    }
                    if(v[i]==2)
                        cr.push('B');
                    i++; break;

                case 'C':
                    if(v[i]==2&&i!=n){
                        g<<0<<'\n';
                        goto stop;
                    }
                    cr.pop();
                    if(v[i]==3){
                         cr.push('C'); cr.push('B');
                    }
                    if(v[i]==1){
                        cr.push('A'); cr.push('2');
                    }
                    i++;
                    break;
            }
        }
        if(!cr.empty())
            g<<0<<'\n';
        else
            g<<1<<'\n';
        stop:;
    }

    return 0;
}