const f='perle.in';g='perle.out';
type stare=record
        stiva:array[1..10000] of char;
        varf:integer;
        valid:boolean;
end;
var
    n,i,l,k,v:integer;
    s:array[1..2] of stare;
    p:string[1];
begin
    assign(input,f);reset(input);
    assign(output,g);rewrite(output);
    readln(n);
    for i:=1 to n do
        begin
        read(l);
        if l=1 then begin
                    writeln(1);
                    readln;
                    continue;
                    end;
        s[1].valid:=true;
        s[1].varf:=1;
        s[1].stiva[1]:='B';
        s[2].valid:=true;
        s[2].varf:=1;
        s[2].stiva[1]:='C';
        while (l>0) and (s[1].valid or s[2].valid)do
            begin
            read(v);
            l:=l-1;
            str(v,p);
            for k:=1 to 2 do
                if (s[k].valid=true) then
                    with s[k] do
                        begin
                        if (stiva[varf] in ['1','2','3']) then
                            if (p<>stiva[varf]) then valid:=false
                                                else varf:=varf-1
                            else
                            if (stiva[varf]='A') then varf:=varf-1
                                else
                                if(stiva[varf]='B') then
                                    begin
                                    if (p='1') then
                                        begin
                                        stiva[varf]:='C';
                                        varf:=varf+1;
                                        stiva[varf]:='A';
                                        varf:=varf+1;
                                        stiva[varf]:='3';
                                        varf:=varf+1;
                                        stiva[varf]:='A';
                                        end;
                                    if (p='3') then valid:=false;
                                    end
                                    else
                                    if (stiva[varf]='C') then
                                        begin
                                        if (p='2') then varf:=varf-1;
                                        if (p='3') then
                                            begin
                                            stiva[varf]:='C';
                                            varf:=varf+1;
                                            stiva[varf]:='B'
                                            end;
                                        if (p='1') then
                                            begin
                                            stiva[varf]:='A';
                                            varf:=varf+1;
                                            stiva[varf]:='2';
                                            end;
                                        end;
                        if (varf>l) then valid:=false;
                        if(varf=0) and (l>0) then valid:=false;
                        end;
            end;
        if ((l=0) and ((s[1].valid=true)and(s[1].varf=0) or
                       (s[2].valid=true)and(s[2].varf=0))) then writeln(1)
                                                          else writeln(0);
        if (l>0) then readln;
        end;
    close(input);close(output);
end.