var a:array[0..10000]of char;
    s,s1:string;
    n,i,j,x,t,y,q,q1,m,c:integer;

function verificare(s:string):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,j:integer;
    s1:string;
begin
     if length(s)>m then
     begin
          exit;
     end;
     if length(s)=m then
     begin
          if verificare(s) then
          begin
               q:=c;
               exit;
          end;
     end;
     for i:=1 to length(s) do
     begin
          s1:=s;
          if s[i]='A' then
          begin
               s1:=s;
               delete(s,i,1);
               insert('1',s,i);
               inc(c);
               df(s);
               dec(c);
               s:=s1;
               if q<>0 then exit;
               delete(s,i,1);
               insert('2',s,i);
               inc(c);
               df(s);
               dec(c);
               s:=s1;
               if q<>0 then exit;
               delete(s,i,1);
               insert('3',s,i);
               inc(c);
               df(s);
               dec(c);
               s:=s1;
               if q<>0 then exit;
          end;
          if s[i]='B' then
          begin
               s1:=s;
               delete(s,i,1);
               insert('2B',s,i);
               inc(c);
               df(s);
               dec(c);
               s:=s1;
               if q<>0 then exit;
               delete(s,i,1);
               insert('1A3AC',s,i);
               inc(c);
               df(s);
               dec(c);
               s:=s1;
               if q<>0 then exit;
          end;
          if s[i]='C' then
          begin
               s1:=s;
               delete(s,i,1);
               insert('2',s,i);
               inc(c);
               df(s);
               dec(c);
               s:=s1;
               if q<>0 then exit;
               delete(s,i,1);
               insert('3BC',s,i);
               inc(c);
               df(s);
               dec(c);
               s:=s1;
               if q<>0 then exit;
               delete(s,i,1);
               insert('12A',s,i);
               inc(c);
               df(s);
               dec(c);
               s:=s1;
               if q<>0 then exit;
          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;
          q1:=0;
          q:=0;
          c:=0;
          df('A');
          if q>0 then q1:=1;
          q:=0;
          c:=0;
          if q1=0 then df('B');
          if q>0 then q1:=1;
          q:=0;
          c:=0;
          if q1=0 then df('C');
          if q>0 then q1:=1;

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