#include <cstdio>
#include <deque>
using namespace std;

int v[10010];
deque <int> q;

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

    int n,m,i,j;
    bool sem;
    scanf("%d",&n);

    for(i=1;i<=n;i++){
        scanf("%d",&m);
        for(j=1;j<=m;j++) scanf("%d",&v[j]);
        sem=0;

        if(m==1){
            printf("1\n");
            continue;
        }
        if(v[1]==1){
            if(m==3 and v[2]==2){
                printf("1\n");
                continue;
            }
            else{
                q.push_front(10);
                q.push_front(3);
                q.push_front(10);
                q.push_front(30);
            }
        }
        if(v[1]==2) q.push_front(20);
        if(v[1]==3){
            q.push_front(20);
            q.push_front(30);
        }

        for(j=2;j<=m;j++){
            if(q.empty()){
                sem=1;
                break;
            }
            if(q.back()<10){
                if(q.back()!=v[j]){
                    sem=1;
                    break;
                }
                q.pop_back();
            }
            else{
                if(q.back()==10) q.pop_back();
                else{
                    if(q.back()==20){
                        q.pop_back();
                        if(v[j]==1){
                            q.push_back(30);
                            q.push_back(10);
                            q.push_back(3);
                            q.push_back(10);
                        }
                        if(v[j]==2) q.push_back(20);
                        if(v[j]==3){
                            sem=1;
                            break;
                        }
                    }
                    else{
                        q.pop_back();
                        if(v[j]==1){
                            q.push_back(10);
                            q.push_back(2);
                        }
                        if(v[j]==3){
                            q.push_back(30);
                            q.push_back(20);
                        }
                    }
                }
            }
        }

        if(sem==1 or !q.empty()) printf("0\n");
        else printf("1\n");
        while(!q.empty()) q.pop_back();
    }

    return 0;
}