var a:array[0..10000]of char;
    n,i,t,y,q,m,p: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:string);
var i:integer;
    s1:string;
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[p]='A' then
          begin
               s1:=s;
               if a[p]='1' then
               begin
                    s[p]:='1';
                    inc(p);
                    df(s);
                    dec(p);
                    s:=s1;
                    if q<>0 then exit;
               end;
               if a[p]='2' then
               begin
                    s[p]:='2';
                    inc(p);
                    df(s);
                    dec(p);
                    s:=s1;
                    if q<>0 then exit;
               end;
               if a[p]='3' then
               begin
                    s[p]:='3';
                    inc(p);
                    df(s);
                    dec(p);
                    s:=s1;
                    if q<>0 then exit;
               end;
          end;
          if s[p]='B' then
          begin
               s1:=s;
               if a[p]='2' then
               begin
                    delete(s,p,1);
                    insert('2B',s,p);
                    inc(p);
                    df(s);
                    dec(p);
                    s:=s1;
                    if q<>0 then exit;
               end;
               if (a[p]='1')and(a[p+2]='3') then
               begin
                    delete(s,p,1);
                    insert('1A3AC',s,p);
                    inc(p);
                    df(s);
                    dec(p);
                    s:=s1;
                    if q<>0 then exit;
               end;
          end;
          if s[p]='C' then
          begin
               s1:=s;
               if a[p]='2' then
               begin
                    s[p]:='2';
                    inc(p);
                    df(s);
                    dec(p);
                    s:=s1;
                    if q<>0 then exit;
               end;
               if a[p]='3' then
               begin
                    delete(s,p,1);
                    insert('3BC',s,p);
                    inc(p);
                    df(s);
                    dec(p);
                    s:=s1;
                    if q<>0 then exit;
               end;
               if (a[p]='1')and(a[p+1]='2') then
               begin
                    delete(s,p,1);
                    insert('12A',s,p);
                    inc(p);
                    df(s);
                    dec(p);
                    s:=s1;
                    if q<>0 then exit;
               end;
          end;
          if s[p]<>a[p] then exit;
     {end;}
     inc(p);
     df(s);
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;
          p:=1;
          df('A');
          p:=1;
          if q=0 then df('B');
          p:=1;
          if q=0 then df('C');

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