program sarkany2;
type sor=array[1..1000] of 1..3;

var n,l,i,j,k,szam:word;
    f,g:text;
    masolas,temp:sor;

procedure masol(x:sor;i,j:word);

begin
szam:=0;

for k:=i to i+j-1 do begin
inc(szam);
masolas[szam]:=x[k];

end;

end;
function c(ll:word;x:sor):boolean; forward;
function a(ll,x:word):boolean;
var jo:boolean;
begin
jo:=false;
if (ll=1) and ((x=1)or(x=2)or(x=3)) then
jo:=true;
a:=jo;
end;

function b(ll:word;x:sor):boolean;
var jo:boolean;
begin
jo:=false;

if (ll>=6) and (x[1]=2) then begin

masol(x,2,ll-1);
if b(ll-1,masolas) then jo:=true;

end;

if (not jo) and (ll>=5) and (x[1]=1) and (x[3]=3) then begin

masol(x,5,ll-4);
if c(ll-4,masolas) then jo:=true;

end;

b:=jo;
end;

function c(ll:word;x:sor):boolean;
var jo:boolean;
    ii:word;
begin
jo:=false;

if (ll=1) and (x[1]=2) then jo:=true;

if (ll=3) and (x[1]=1) and (x[2]=2) and ((x[3]=1)or(x[3]=2)or(x[3]=3)) then
jo:=true;

if (ll>=7) and (x[1]=3) and (not jo) then begin

   for ii:=2 to ll-1 do begin
       if not jo then begin
       masol(x,2,ii-1);
       if b(ii-1,masolas) then begin
        masol(x,ii+1,ll-ii);
        if c(ll-ii,masolas) then jo:=true;

       end;

    end;
   end;

end;


c:=jo;
end;

begin
    assign(f,'perle.in');reset(f);
    assign(g,'perle.out');rewrite(g);
    readln(f,n);

    for i:=1 to n do begin
        read(f,l);
        for j:=1 to l do
        read(f,temp[j]);
        readln(f);
        if ((l=1)and((temp[1]=1)or(temp[1]=2)or(temp[1]=3)))or(b(l,temp))or(c(l,temp)) then
        writeln(g,'1') else writeln(g,'0');


    end;



   close(f);
   close(g);

end.