Program cel;  
Type vector=array[1..15000] of integer;  
var f,g:text;  
    a:vector;  
    n,i,j,nr,l,m,k:integer;  
    stop:boolean;  
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);  
  stop:=false;  
  For k:=1 to m do a[k]:=0;  
  m:=0;  
  If l=1 then Begin  
               Readln(f,nr);  
               If (1>nr) and (nr>3) then Begin  
                                          stop:=true;  
                                          break;  
                                         end;  
               m:=1;  
              end  
         else Begin  
               For j:=1 to l do  
                Begin  
                 Read(f,nr);  
                 If (nr<1) or (nr>3) then Begin  
                                           stop:=true;  
                                           break;  
                                          end  
                                     else  
                 If (a[j]=0) and (j=1) then Begin  
                                 If nr=1 then If l<3 then Begin  
                                                           stop:=true;  
                                                           break;  
                                                          end  
                                                     else  
                                 If l=3 then Begin  
                                                  a[j]:=1;  
                                                  a[j+1]:=2;  
                                                  a[j+2]:=ord('A');  
                                                  inc(m,3);  
                                                 end  
                                             else If l<5 then Begin  
                                                               stop:=true;  
                                                               break;  
                                                              end  
                                                         else Begin  
                                                                   a[j]:=1;  
                                                                   a[j+1]:=ord('A');  
                                                                   a[j+2]:=3;  
                                                                   a[j+3]:=ord('A');  
                                                                   a[j+4]:=ord('C');  
                                                                   inc(m,5);  
                                                                  end;  
                                If nr=2 then  Begin  
                                               a[j]:=2;  
                                               a[j+1]:=ord('B');  
                                               inc(m,2);  
                                              end;  
                                If nr=3 then If l<3 then Begin  
                                                          stop:=true;  
                                                          break;  
                                                         end  
                                                     else Begin  
                                                           a[j]:=3;  
                                                           a[j+1]:=ord('B');  
                                                           a[j+2]:=ord('C');  
                                                           inc(m,3);  
                                                          end;  
                                end  
                           else Begin  
                                 If a[j]=0 then Begin  
                                                 stop:=true;  
                                                 break;  
                                                end  
                                           else  
                                 If ((1<=a[j]) and (a[j]<=3)) then  
                                  If nr<>a[j] then Begin  
                                                    stop:=true;  
                                                    break;  
                                                   end;  
  
                                   If chr(a[j])='A' then a[j]:=nr;  
                                   If chr(a[j])='B' then  
                                    Begin  
                                     If nr=3 then Begin  
                                                   stop:=true;  
                                                   break;  
                                                  end;  
                                     If nr=2 then If l-m+1<2 then Begin  
                                                                   stop:=true;  
                                                                   break;  
                                                                  end  
                                                              else Begin  
                                                                    For k:=m downto j+1 do  
                                                                     a[k+1]:=a[k];  
                                                                    a[j]:=2;  
                                                                    a[j+1]:=ord('B');  
                                                                    inc(m);  
                                                                   end;  
                                     If nr=1 then If l-m+1<5 then Begin  
                                                                   stop:=true;  
                                                                   break;  
                                                                  end  
                                                              else Begin  
                                                                    For k:=m downto j+1 do  
                                                                     a[k+4]:=a[k];  
                                                                    a[j]:=1;  
                                                                    a[j+1]:=ord('A');  
                                                                    a[j+2]:=3;  
                                                                    a[j+3]:=ord('A');  
                                                                    a[j+4]:=ord('C');  
                                                                    inc(m,4);  
                                                                   end;  
                                    end;  
                                 If chr(a[j])='C' then Begin  
                                  If nr=2 then a[j]:=2;  
                                  If nr=3 then If l-m+1<3 then Begin  
                                                                stop:=true;  
                                                                break;  
                                                               end  
                                                          else Begin  
                                                                For k:=m downto j+1 do  
                                                                     a[k+2]:=a[k];  
                                                                a[j]:=3;  
                                                                a[j+1]:=ord('B');  
                                                                a[j+2]:=ord('C');  
                                                                inc(m,2);  
                                                               end;  
                                  If nr=1 then If ((l-j+1>3) or (l-j+1<3)) and (j=m) then Begin  
                                                                stop:=true;  
                                                                break;  
                                                               end  
                                                          else Begin  
                                                                For k:=m downto j+1 do  
                                                                     a[k+2]:=a[k];  
                                                                a[j]:=1;  
                                                                a[j+1]:=2;  
                                                                a[j+2]:=ord('A');  
                                                                inc(m,2);  
                                                               end;  
  
                                 end;  
                                end;  
                end;  
               Readln(f);  
              end;  
  If stop then Writeln(g,0)  
          else If m<>l then Writeln(g,0)  
                       else Writeln(g,1);  
 end;  
Close(f);  
Close(g);  
end.