{100 PUNCTE}
var fi,fo:text;
    i,j,t,n:integer;
    a,c:array[1..10000] of byte;
    vf,k,rezer:integer;
    cr:char;
    ok:boolean;

  procedure solve;
   var i,j,k,p:integer;
        empty:boolean;
        cst,crr:char;
        vl:integer;
    begin
     if (a[1]=2) and (n>1) and (n<5) then
      begin
       writeln(fo,0);
       exit;
      end;
     if (a[1]=1) and (n>1) and (n<>3) and (n<5) then
      begin
       writeln(fo,0);
       exit;
      end;
    cr:='X';
     empty:=false;
    while empty=false do
     begin
      cst:=cr;
      vl:=vf;
      p:=c[vf];
      if (p=1) and (vf=1) and (cr in [('A'),('X')]) then
       begin
        writeln(fo,1);
        exit;
       end;
      if (p=2) and (vf=1) and (cr in [('A'),('C'),('X')]) then
       begin
        writeln(fo,1);
        exit;
       end;
      if (p=3) and (vf=1) and (cr in [('A'),('X')]) then
       begin
        writeln(fo,1);
        exit;
       end;
      if (p=1) and (vf=3) and (c[vf-1]=2) then
       begin
        writeln(fo,1);
        exit;
       end;
      if cr in[('B'),('X')] then
      if (p=1) and (vf>=5) then
        if c[vf-2] = 3 then
         begin
          dec(vf,4);
          crr:='C';
         end
        else
         begin
          writeln(fo,0);
          exit;
         end;
      if cr in[('B'),('X')] then
      if (p=2) and (vf>5) then
         begin
          dec(vf);
          crr:='B';
         end;
      if cr in[('C')] then
       if (p=2) then
        begin
         dec(vf);
         if rezer>0 then dec(rezer)
          else if vf>0 then break;
        end;

      if (p=1) and (c[vf-1]=2) and (cr='C') then
        begin
         dec(vf,3);
         if rezer>0 then dec(rezer)
          else if vf>0 then break;
        end;


      if (p=3) and (c[vf-1]=3) then
       begin
        writeln(fo,0);
        exit;
       end;
      if (p=3) and (c[vf-1]<>3) then
        begin
         dec(vf);
         crr:='B';
         inc(rezer);
        end;
      if vf=0 then empty:=true;
      if (cst=cr) and (rezer>0) and (vl=vf) then
       begin
        crr:='C';
        dec(rezer);
       end else
      if (cst=cr) and (rezer=0) and (vl=vf) then
       begin
        break;
       end;
      cr:=crr;
     end;
    if empty=true then writeln(fo,1)
      else writeln(fo,0);
   end;



begin
 assign(fi,'perle.in'); reset(fi);
 assign(fo,'perle.out'); rewrite(fo);
 readln(fi,t);
 for i:=1 to t do
  begin
   read(fi,n);
   k:=n;
   vf:=n;
   for j:=1 to n do
    begin
     read(fi,a[j]);
     if not a[j]  in[(1),(2),(3)] then
      begin
       break;
       ok:=true;
      end;
     c[k]:=a[j];
     dec(k);
    end;
   if ok=true then
    begin
     writeln(fo,0);
     break;
    end;
   solve;
  end;
 close(fo);
 close(fi);
end.