Program Perle;
type sir=array[1..10001] of byte;
var a:sir;
    f,g:text;
    l,j:integer;
    n,i:byte;
Function c(a:sir;l,x:integer):integer;
         forward;
Function b(a:sir;l,x:integer):integer;
begin
     If l-x<4 then b:=0
              else
                If (a[x]=1) and (a[x+2]=3) then b:=c(a,l,x+4)
                                           else
                                           If a[x]=2 then b:=b(a,l,x+1);
end;
Function c(a:sir;l,x:integer):integer;
var aux:integer;
begin
     If a[x]=2 then c:=x+1
               else
               If (a[x]=1) and (a[x+1]=2) and (l-x>=2) then c:=x+3
                   else
                   begin
                  If (l-x>=6) and (a[x]=3) then begin
                                                aux:=b(a,l,x+1);
                                                If aux=0 then c:=aux
                                                         else c:=c(a,l,aux);
                   end;                         end;
end;
begin
  assign(f,'perle.in');reset(f);
  assign(g,'perle.out');rewrite(g);
  readln(f,n);
  For i:=1 to n do
      begin
      read(f,l);
      For j:=1 to l do read(f,a[j]);
      If (l=1) or (b(a,l,1)-1=l) or (c(a,l,1)-1=l) then writeln(g,1)
                                                   else writeln(g,0);



     readln(f);
     end;
  close(f);
  close(g);
end.