program perle;
type str2 = string[10];
type vector = array [1..5000] of Char;
var fin,fout:text;
    i,j,n,q,m,vn,xn,t:longint;
    v,x:vector;
    car:char;
    ok1,ok2,ok3:boolean;
{*-------------------------*}
procedure insert2(var x:vector; var xn:integer; index:integer; s:str2);
var c:integer;
begin
   for i:=xn+length(s) downto index do
   begin
      x[i]:=x[i-length(S)+1];
   end;

   c:=0;
   for i:=index to index+length(s)-1 do
   begin
      inc(c);
      x[i]:=s[c];
   end;
   xn:=xn+length(s)-1;
end;
{*-------------------------*}
function back(x:vector; xn:integer):boolean;
//var i,j:integer;
begin
   back:=false;
   if xn <= vn then
   begin
      j:=1;
      while (x[j] = v[j]) and (j<=vn) do inc(j);
      i:=j;
      if j > vn then back:=true;

      if (x[j] = 'A') then
      begin
         if v[j] = '1' then
         begin
            x[j]:='1';
            back:=back(x,xn);
         end
         else
         if v[i] = '2' then
         begin
            x[j]:='2';
            back:=back(x,xn);
         end
         else
         if v[i] = '3' then
         begin
            x[j]:='3';
            back:=back(x,xn);
         end
         else
      end;
      if x[j] = 'B' then
      begin
         if v[j] = '2' then
         begin
            insert2(x,xn,j,'2B');
            back:=back(x,xn);
         end
         else
         if v[j] = '1' then
         begin
            insert2(x,xn,j,'1A3AC');
            back:=back(x,xn);
         end
         else
      end;
      if x[j] = 'C' then
      begin
         if v[j] ='2' then
         begin
            x[j]:='2';
            back:=back(x,xn);
         end
         else
         if v[j] = '3' then
         begin
            insert2(x,xn,j,'3BC');
            back:=back(x,xn);
         end
         else
         if v[j] = '1' then
         begin
            insert2(x,xn,j,'12A');
            back:=back(x,xn);
         end
         else
      end;
   end;
end;
{*-------------------------*}
begin
   assign(fin,'perle.in'); reset(fin); assign(fout,'perle.out'); rewrite(fout);

   readln(fin,t);
   for q:=1 to t do
   begin
      read(fin,vn);
      for i:=1 to vn do
      begin
         read(fin,car);
         read(fin,v[i]);
      end;

      xn:=1;
      x[1]:='A';
      ok1:=back(x,xn);

      xn:=1;
      x[1]:='B';
      ok2:=back(x,xn);

      xn:=1;
      x[1]:='C';
      ok3:=back(x,xn);

      if (ok1) or (ok2) or (ok3) then writeln(fout,1)
      else writeln(fout,0);
   end;

   close(fin); Close(fout);
end.