using namespace std;

#include<iomanip>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<utility>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<numeric>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<deque>

const int INFI=(1LL<<30)-100;
const long long INFL=(1LL<<62);
const double eps=1e-10;
const long double pi=acos(-1.0);
const int MAXL=10001;

int sz;
string perl;
stack<char> q;

bool recurence(int i){
    if(i==sz){
        if(!q.empty()){
            return 0;
        }
        return 1;
    }

    if(q.top()==perl[i]){
        q.pop();
        return recurence(i+1);
    }else{
        char ch=q.top();
        q.pop();
        switch(ch){
            case 'A':
                q.push(perl[i]);
                return recurence(i);
                break;

            case 'C':
                if(perl[i]=='2'){
                    q.push('2');
                    return recurence(i);
                }else if(perl[i]=='1' && perl[i+1]=='2'){
                    q.push('A');
                    q.push('2');
                    q.push('1');
                    return recurence(i);
                }else if(perl[i]=='3'){
                    q.push('C');
                    q.push('B');
                    q.push('3');
                    return recurence(i);
                }
                break;
            case 'B':
                if(perl[i]=='1'){
                    q.push('C');
                    q.push('A');
                    q.push('3');
                    q.push('A');
                    q.push('1');
                    return recurence(i);
                }else if(perl[i]=='2'){
                    q.push('B');
                    q.push('2');
                    return recurence(i);
                }
                break;
        }
    }

    return 0;
}

int main(){
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);

    int tt;
    scanf("%d",&tt);

    while(tt--){
        scanf("%d",&sz);
        perl.clear();
        for(int i=1;i<=sz;i++){
            int nr;
            scanf("%d",&nr);
            perl.push_back(nr+'0');
        }

        if(sz<=3){
            if(sz==1){
                printf("1\n");
                continue;
            }
            if(sz==3 && perl[0]=='1' && perl[1]=='2'){
                printf("1\n");
                continue;
            }
            printf("0\n");
            continue;
        }

        if(perl[0]=='1' || perl[0]=='2'){
            q.push('B');
        }else{
            q.push('C');
        }

        printf("%d\n",(int)recurence(0));
        while(!q.empty()){
            q.pop();
        }
    }


    return 0;
}