#include <fstream>
#include <stack>
using namespace std;
ifstream fin("perle3.in");
ofstream fout("perle3.out");
int t,n,a[10005],q,i,j;
stack <int>S;
bool ok;
int main()
{fin>>t;
 for(i=1;i<=t;i++)
    {fin>>n;
     ok=0;
     for(j=1;j<=n;j++)
        fin>>a[j];
     q=1;
     if(n==1)fout<<"1 \n";
     else if(n>1)
            {if(a[1]==1&&n==3){S.push(-1);S.push(2);S.push(1);
                               q++;}
             else if(a[1]==1) {S.push(-3);S.push(-1);S.push(3);S.push(-1);S.push(1);
                               q++;}
             else if(a[1]==2) {S.push(-2);S.push(2);
                               q++;}
             else if(a[1]==3) {S.push(-3);S.push(-2);S.push(3);
                               q++;}
            S.pop();
     while(q<=n)
          {if(a[q]==1){if(S.top()==1){q++;S.pop();}
                       else if(S.top()==-1){q++;S.pop();}
                       else if(S.top()==-2){q++;S.pop();S.push(-3);S.push(-1);S.push(3);S.push(-1);}
                       else if(S.top()==-3){q++;S.pop();S.push(-1);S.push(2);}
                       else {ok=1;break;}
                      }
           else if(a[q]==2){if(S.top()==2){q++;S.pop();}
                            else if(S.top()==-1){q++;S.pop();}
                            else if(S.top()==-2){q++;S.pop();S.push(-2);}
                            else if(S.top()==-3){q++;S.pop();}
                            else {ok=1;break;}
                           }
           else if(a[q]==3){if(S.top()==3){q++;S.pop();}
                            else if(S.top()==-1){q++;S.pop();}
                            else if(S.top()==-3){q++;S.pop();S.push(-3);S.push(-2);}
                            else {ok=1;break;}
                           }
            if(q==n+1&&S.size()>0){ok=1;break;}
          }
          if(ok==0)fout<<"1 \n";
          else fout<<"0 \n";
            }
            while(S.size()>0)S.pop();
    }
}