program perle;
var f,g:text;
    a:array[0..10005] of longint;
    t,n,i,j:longint;
    bufin,bufout:array[1..65000] of byte;

function b(x:longint):longint; forward;

function c(x:longint):longint;
var u:longint;
begin
 if x>n then c:=0
 else
 if (a[x]=1) or(a[x+1]=2) then c:=x+2
 else
 if (a[x]=2) then c:=x
 else
  if (a[x]=3) then
  begin
   u:=b(x+1);
   if u<>0 then c:=c(u+1);
  end;
end;

function b (x:longint):longint;
begin
 if x>n then b:=0
 else
  if (a[x]=1) or (a[x+2]=3) then b:=c(x+4)
  else
  if (a[x]=2) then b:=b(x+1);
end;

begin
 assign (f,'perle.in'); reset (F);
 assign(g,'perle.out'); rewrite (G);
 settextbuf (f,bufin);
 settextbuf (g,bufout);
 readln (f,t);
 for j:=1 to t do
 begin
  read (f,n);
  for i:=1 to n do
   read (f,a[i]);
  readln (F);
  if (n=1) or (n=b(1)) or (n=c(1)) then writeln (g,1)
  else writeln (g,0);
 end;
 close (F); close (g);
end.