peg

Peg Solitaire este un joc pentru un singur jucător. Tabla de joc este o bandă cu $N$ poziţii. Pe fiecare poziţie poate fi plasat un singur jeton.

Orice configuraţie de joc poate fi codificată ca o secvenţă binară de lungime $N$, unde $1$ reprezintă un jeton, iar $0$ reprezintă o poziţie liberă.

O mutare este un salt la stânga sau un salt la dreapta.

În saltul la dreapta jetonul de pe poziţia $i$ sare peste jetonul de pe poziţia $i+1$; jetonul de pe poziţia $i+1$ este eliminat; jetonul de pe poziţia $i$ ajunge pe poziţia $i+2$ (aceasta trebuie să fie liberă).

În saltul la stânga jetonul de pe poziţia $i$ sare peste jetonul de pe poziţia $i-1$; jetonul de pe poziţia $i-1$ este eliminat; jetonul de pe poziţia $i$ ajunge pe poziţia $i-2$ (aceasta trebuie să fie liberă).

De exemplu:
În configuraţia $011$ sare la stânga jetonul de pe poziţia $3$ peste jetonul de pe poziţia $2$ şi se obţine configuraţia $100$.
În configuraţia $110$ sare la dreapta jetonul de pe poziţia $1$ peste jetonul de pe poziţia $2$ şi se obţine configuraţia $001$.

Jocul se termină cu succes atunci când pe tablă rămâne un singur jeton.

Cerinţă

Dat fiind un set de configuraţii, să se determine pentru care configuraţii din set jocul se termină cu succes.

Date de intrare

Fişierul de intrare peg.in conţine pe prima linie un număr natural nenul $T$, reprezentând numărul de configuraţii din fişier. Pe fiecare dintre următoarele $T$ linii se află câte o secvenţă binară reprezentând o configuraţie de joc.

Date de ieşire

Fişierul de ieşire peg.out va conţine $T$ linii, câte una pentru fiecare configuraţie. Pe linia $i$ va fi scrisă cifra $1$ dacă pentru cea de a $i$-a configuraţie din fişierul de intrare jocul se termină cu succes, respectiv cifra $0$ în caz contrar.

Restricții și precizări

• $1 \leq T \leq 10$
• $1 \leq$ Lungimea oricărei configuraţii $\leq 150 \ 000$

Exemplu

peg.in

5 
1 
110
001111010
1101110
11

peg.out

1 
1 
1 
0 
0

Explicație

Configuraţia $1$: jocul se termină cu succes în $0$ mutări.
Configuraţia $110$: jocul se termină cu succes într-o singură mutare (primul jeton sare peste cel de al doilea)
Configuraţia $001111010$: jocul se termină cu succes în $4$ mutări
$001111010 \rightarrow 001100110 \rightarrow 000010110 \rightarrow 000011000 \rightarrow 000100000$