var a:array[0..10000]of char;
    s:ansistring;
    n,i,t,y,q,m:integer;

function verificare(s:ansistring):boolean;
var i:integer;
begin
     verificare:=true;
     for i:=1 to length(s) do
     begin
          if a[i]<>s[i] then
          begin
               verificare:=false;
               exit;
          end;
     end;
end;

procedure df(s:ansistring);
var i,j:integer;
    s1:ansistring;
begin
     if length(s)>m then
     begin
          exit;
     end;
     if length(s)=m then
     begin
          if verificare(s) then
          begin
               q:=1;
               exit;
          end;
     end;
     for i:=1 to m do
     begin
          s1:=s;
          if s[i]='A' then
          begin
               s1:=s;
               if a[i]='1' then
               begin
                    delete(s,i,1);
                    insert('1',s,i);
                    df(s);
                    s:=s1;
                    if q<>0 then exit;
               end;
               if a[i]='2' then
               begin
                    delete(s,i,1);
                    insert('2',s,i);
                    df(s);
                    s:=s1;
                    if q<>0 then exit;
               end;
               if a[i]='3' then
               begin
                    delete(s,i,1);
                    insert('3',s,i);
                    df(s);
                    s:=s1;
                    if q<>0 then exit;
               end;
          end;
          if s[i]='B' then
          begin
               s1:=s;
               if a[i]='2' then
               begin
                    delete(s,i,1);
                    insert('2B',s,i);
                    df(s);
                    s:=s1;
                    if q<>0 then exit;
               end;
               if (a[i]='1')and(a[i+2]='3') then
               begin
                    delete(s,i,1);
                    insert('1A3AC',s,i);
                    df(s);
                    s:=s1;
                    if q<>0 then exit;
               end;
          end;
          if s[i]='C' then
          begin
               s1:=s;
               if a[i]='2' then
               begin
                    delete(s,i,1);
                    insert('2',s,i);
                    df(s);
                    s:=s1;
                    if q<>0 then exit;
               end;
               if a[i]='3' then
               begin
                    delete(s,i,1);
                    insert('3BC',s,i);
                    df(s);
                    s:=s1;
                    if q<>0 then exit;
               end;
               if (a[i]='1')and(a[i+1]='2') then
               begin
                    delete(s,i,1);
                    insert('12A',s,i);
                    df(s);
                    s:=s1;
                    if q<>0 then exit;
               end;
          end;
          if s[i]<>a[i] then break;
     end;
end;

begin
     assign(input,'perle.in');
     reset(input);
     assign(output,'perle.out');
     rewrite(output);
     readln(n);
     for t:=1 to n do
     begin
          read(m);
          for i:=1 to m do
          begin
               read(y);
               a[i]:=chr(ord('0')+y);
          end;
          q:=0;
          df('A');
          if q=0 then df('B');
          if q=0 then df('C');

          writeln(q);
     end;
close(output);
end.