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-j+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-j+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-j+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) then begin
                                                                stop:=true;
                                                                break;
                                                               end
                                                          else begin
                                                                bor 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;
               beadln(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.