var a:array[0..10000]of char;
    n,i,j,m,y,q,pz,q1,t:longint;

procedure perlaa;forward;
procedure perlab;forward;
procedure perlac;forward;

procedure perlaa;
begin
     if pz>m then q1:=0;
     inc(pz);
end;

procedure perlab;
begin
     if (a[pz]='2')and(pz+1<=m) then
     begin
          if pz>m then
          begin
               q1:=0;
               exit;
          end;
          inc(pz);
          perlab;
          if q1=0 then exit;
     end;
     if (a[pz]='1')and(pz+3<=m) then
     begin
          if pz>m then
          begin
               q1:=0;
               exit;
          end;
          inc(pz);
          perlaa;
          if q1=0 then exit;
          if a[pz]='3' then
          begin
               if pz>m then
               begin
                    q1:=0;
                    exit;
               end;
               inc(pz);
          end
          else
          begin
               q1:=0;
               exit;
          end;
          if pz>m then
          begin
               q1:=0;
               exit;
          end;
          perlaa;
          if pz>m then
          begin
               q1:=0;
               exit;
          end;
          perlac;

     end;
end;


procedure perlac;
begin
     if a[pz]='2' then
     begin
          inc(pz);
          if pz>m then
          begin
               q1:=0;
               exit;
          end;
     end;
     if (a[pz]='3')and(pz+2<=m) then
     begin
          inc(pz);
          if pz>m then
          begin
               q1:=0;
               exit;
          end;
          perlab;
          if pz>m then
          begin
               q1:=0;
               exit;
          end;
          perlac;
     end;
     if (a[pz]='1')and(pz+2<=m) then
     begin
          inc(pz);
          if pz>m then
          begin
               q1:=0;
               exit;
          end;
          if a[pz]='2' then
          begin
               inc(pz);
               if pz>m then
               begin
                    q1:=0;
                    exit;
               end;
          end
          else
          begin
               q1:=0;
               exit;
          end;
          if pz>m then
          begin
               q1:=0;
               exit;
          end;
          perlaa;
     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;
          q1:=1;
          pz:=1;
          perlaa;
          if (pz=m+1)and(q1=1) then
          begin
               q:=1;
          end;
          pz:=1;
          q1:=1;
          if q=0 then perlab;
          if (pz=m+1)and(q1=1) then
          begin
               q:=1;
          end;
          pz:=1;
          q1:=1;
          if q=0 then perlac;
          if (pz=m+1)and(q1=1) then
          begin
               q:=1;
          end;
          writeln(q);
     end;
close(output);
end.