var a,b:array[1..10000] of char; ind,i,j,n,ok,lu:longint; f1,f2:text; c:char;

procedure cc2;forward;
procedure bb2;forward;

procedure cc3;
begin
inc(ind);
b[ind]:='1';
inc(ind);
b[ind]:='2';
inc(ind);
b[ind]:='a';
end;

procedure cc1;
begin
inc(ind);
b[ind]:='2';
end;

procedure bb2;
begin
inc(ind);
b[ind]:='1';
inc(ind);
b[ind]:='a';
inc(ind);
b[ind]:='3';
inc(ind);
b[ind]:='a';
if a[ind+1]='3' then cc2
else if a[ind+1]='2' then cc1
else if a[ind+1]='1' then cc3;
end;

procedure bb1;
begin
inc(ind);
b[ind]:='2';
if a[ind+1]='2' then bb1
else if a[ind+1]='1' then bb2;
end;

procedure cc2;
begin
inc(ind);
b[ind]:='3';
if a[ind+1]='2' then bb1
else if a[ind+1]='1' then bb2;
if (a[ind+1]='1')and(ind+3=lu) then cc3
else if a[ind+1]='3' then cc2
else if (a[ind+1]='2')and(ind+1=lu) then cc1;
end;

procedure start;
begin
ind:=0;
if (a[1]='1')and(lu=3) then cc3;
if a[1]='2' then bb1;
if a[1]='3' then cc2;
if (a[1]='1')and(lu<>3) then bb2;
end;

begin
        assign(f1,'perle.in');
        reset(f1);
        assign(f2,'perle.out');
        rewrite(f2);
        read(f1,n);
        for i:=1 to n do begin
                read(f1,lu);
                ok:=0;
                if (lu=2)or(lu=4) then begin readln(f1); writeln(f2,0); end
                        else if lu=1 then begin readln(f1); writeln(f2,1) end
                                else begin
                                        for j:=1 to lu do begin read(f1,c); read(f1,a[j]); end;
                                        start;
                                        if ind<>lu then ok:=1
                                        else for j:=1 to lu do if (a[j]<>b[j])and(b[j]<>'a') then ok:=1;
                                        if ok=1 then writeln(f2,0)
                                                else writeln(f2,1);
                                        end;
        end;
        close(f1);
        close(f2);
end.