program pascal;
   var a:array[1..10010] of integer;
        f,g:text;
        i,n,t:longint;
    function perlab(x:longint):boolean; forward;
    function perlac(x:longint):boolean; forward;
    function perlab(x:longint):boolean;
       begin
       if a[x]=2 then begin perlab:=perlab(x+1); exit;end
          else  if (a[x]=1) and (a[x+2]=3) then
              begin perlab:=perlac(x+4); exit; end;
       perlab:=false;
      end;
   function perlac(x:longint):boolean;
    begin
           if x=n+1 then begin  perlac:=true; exit; end;
           if a[x]=2 then begin perlac:=perlac(x+1); exit; end;
           if (a[x]=1) and (a[x+1]=2) then begin  perlac:=perlac(x+3); exit; end;
           if a[x]=3 then begin perlac:=perlab(x+1); exit; end;
           perlac:=false;
    end;
   procedure rasp(ok:boolean);
    begin
           if ok then writeln(g,1)
           else       writeln(g,0);
    end;

   procedure solve;
    var ok:boolean;
    begin
           ok:=false;
           read(f,n);
           for i:=1 to n do read(f,a[i]);
           if n=1 then begin rasp(true); exit; end;
          if n=2 then begin  rasp(false); exit; end;
           if (a[1]=3) then begin ok:=perlac(1); rasp(ok); exit; end;
           if (n>=4) and (a[1]=1) and (a[3]=3) then
            begin ok:=perlab(1); rasp(ok); exit; end;
           if (a[1]=1) and (a[2]=2) then
               begin ok:=perlac(1); rasp(ok); exit; end;
           if (a[1]=2) then
               begin ok:=perlab(1); rasp(ok); exit; end;
          rasp(false);
    end;
   begin
    assign(f,'perle.in'); reset(f);   assign(g,'perle.out'); rewrite(g);
    read(f,t);
    while t<>0 do
        begin
           solve;
           t:=t-1;
       end;
    close(f); close(g);
  end.