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.