#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

ifstream fin("perle.in");ofstream fout("perle.out");
#define cin fin
#define cout fout

int t, n, m, k, a[300010], q, l, r;

int32_t main(){
INIT
cin>>t;

while(t--){
    cin>>n;
    for(int i=1; i<=n; i++){cin>>a[i];}
    if(n==2){cout<<0<<"\n"; continue;}
    if(n==3){ if((a[1]!=1) || (a[2]!=2) ){cout<<"0\n"; continue;}cout<<"1\n"; continue; }
    if(n==1){cout<<"1\n"; continue;}
    int cnt=1;
    int i=1;
    if(a[i]!=3){
    while(a[i]==2){
        i++;
    }
    if(i>n){cout<<"0\n"; goto Next;}
    if(a[i]!=1){cout<<"0\n"; goto Next;}i+=2; if(i>n){cout<<"0\n"; goto Next;}
    if(a[i]!=3){cout<<"0\n"; goto Next;}i+=2; if(i>n){cout<<"0\n"; goto Next;}
    }

    while(cnt>0){
        if(i>n){cout<<"0\n"; goto Next;}
        if(a[i]==1){
            if( (i+2)<=n){if(a[i+1]!=2){cout<<"0\n"; goto Next;} i+=3; cnt--; }else{cout<<"0\n"; goto Next;}
        continue;
        }
        if(a[i]==2){
            cnt--;i++; continue;
        }
        if(a[i]==3){
            cnt++;
            i++;
            while(a[i]==2){i++;}
            if(i>n){cout<<"0\n"; goto Next;}
            if(a[i]==1){i+=2;}else{cout<<"0\n"; goto Next;}if(i>n){cout<<"0\n";goto Next;}
            if(a[i]!=3){cout<<"0\n"; goto Next;}i+=2;
        }else{break;}
    }

    if(cnt>0){cout<<"0\n"; goto Next;}
    cout<<"1\n";

    Next:continue;
}




return 0;
}