PROGRAM PERLE;
{Infoarena & OJI 2004 - Clasa a X-a}
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];
    F,G:TEXT;
{---------------------------------}
(*
Ideea de rezolvare este urmatoarea:
  Pentru fiecare secventa,i, din fisier, i=1,n, se incepe generarea ei
in trei cazuri:
- daca lungimea, L, ei este 1, atunci se foloseste doar perla magica A;
- daca L>1 atunci se poate incepe fie cu perla magica de tip B, fie cu C.
Apoi se citeste pe rand cate o valoare din cele L ale secventei din fisier.
Pentru a continua generarea secventei tinem cont de urmatoarele reguli de
inlocuire a perlelor magice A,B si C:

         A -> 1 | 2 | 3
         B -> 2B | 1A3AC
         C -> 2 | 3BC | 12A

OBSERVATIE: Fiecare perla magica poate fi inlocuita de o varianta care
incepe cu o cifra, iar pe deasupra fiecare incepe cu o cifra DIFERITA!
  Daca cifra citita din fisier este caracterul P, atunci exista cel mult
o singura varianta cu care sa se inlocuiasca perla magica curenta astfel ca
valoarea ei de inceput sa fie egala cu cifra citita, P, deci NU apar
ramificatii a starilor in procesul de generare a secventei!
  De mai sus deducem ca exista DOAR doua "stari" cu care se lucreaza
pentru generarea secventei din fisier, si anume:
       - S[1] , stare care se genereaza din perla magica B;
       - S[2] , stare care se genereaza din perla magica C.
  Folosim variabilele:
       - S[K].STIVA = stiva de generare ce corespunde starii S[K], K=1,2,
                      in procesul de generare a secventei.
                        Stiva contine perlele (normale si magice) care au
                      mai ramas in procesul de generare (NU toata secventa
                      generata deja), la VARF fiind perla curenta din care
                      trebuie sa generam valoarea, P, citita din fisier.
       - S[K].VALID = este o valoare booleana ce indica daca starea S[K]
                      K=1,2, mai poate fi folosita pentru a continua
                      procesul de generare a secventei.
                        Daca la un moment dat NU se poate obtine cifra P
                      din perla STIVA[VARF], atunci NU se va putea genera
                      secventa folosind starea S[K], care NU este valida,
                      si pe care nu o vom mai folosi pentru generare!

  Perlele "normale"(1,2,3) din varful stivei, care corespund valorii citite P
din secventa, sunt eliminate din stiva, iar perlele "magice"(A,B,C) sunt
inlocuite in stiva de varianta care incepe cu cifra P, daca exista.
Daca nu exista o varianta care incepe cu cifra P, pentru perle magice,
sau este o perla normala diferita de P, atunci VALID:=FALSE.
(Cifra P cu care incepe varianta de inlocuire a perlei magice, NU se mai
adauga in stiva!). Perlele se adauga in stiva in ordinea inversa in care
apar in varianta de inlocuire a perlei magice STIVA[VARF].
  Acest procedeu se aplica tuturor starilor ramase valide dintre S[K], K=1,2,
pentru fiecare valoare citita P, atata timp cat mai avem valori in secventa,
(deci L>0) si cat timp mai avem stari valide in procesul de generare a
secventei din fisier.
  Alte conditii interne impuse celor doua stari:
     - S[K].VARF <= L;  (pentru eficienta!)
     - S[K].VARF > 0, daca L>0.  (pentru generarea integrala a secventei!)
     - Secventa poate fi generata (conditia de solutie) daca: s-au generat
       toate valorile din secventa (adica L=0), si daca exista o stare
       dintre S[1] si S[2] care este valida si stiva corespunzatoare starii
       respective s-a epuizat (nu mai avem ce genera).
OBS.: Daca nu ar fi cazul particular de inlocuire a perlelor magice cu
variante care incep cu cifre DISTINCTE, atunci nu am genera "liniar",
ci s-ar "ramifica" starile generate, in acest caz vom folosi metoda
"BRANCH AND BOUND" ("Ramifica si Margineste").
*)
{---------------------------------}
BEGIN
ASSIGN(F,'perle.in');
ASSIGN(G,'perle.out');
RESET(F);
REWRITE(G);
READLN(F,N);
FOR I:=1 TO N DO
    BEGIN
    READ(F,L);
    IF L=1 THEN BEGIN
                WRITELN(G,1);
                readln(f);   {!!!}
                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(F,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='2') THEN ;   (* Stiva ramane la fel! *) }
                 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(G,1)
                                                       ELSE WRITELN(G,0);
    if (L>0) then readln(f);   {!!! Se trece pe linia urmatoare in fisier!}
    END;
CLOSE(F);
CLOSE(G);
END.