peg

Peg

Orice configuratie de joc poate fi codificata ca o secventa binara de lungime $N$, unde $1$ reprezinta un jeton, iar $0$ reprezinta o pozitie libera.
O mutare este un salt la stanga sau un salt la dreapta.

In saltul la dreapta jetonul de pe pozitia $i$ sare peste jetonul de pe pozitia $i+1$; jetonul de pe pozitia $i+1$ este eliminat; jetonul de pe pozitia $i$ ajunge pe pozitia $i+2$ (aceasta trebuie sa fie libera).
In saltul la stanga jetonul de pe pozitia $i$ sare peste jetonul de pe pozitia $i-14; jetonul de pe pozitia $i-1$ este eliminat; jetonul de pe pozitia $i$ ajunge pe pozitia $i-2$ (aceasta trebuie sa fie libera).

 
* In saltul la dreapta jetonul de pe pozitia $i$ sare peste jetonul de pe pozitia $i+1$; jetonul de pe pozitia $i+1$ este eliminat; jetonul de pe pozitia $i$ ajunge pe pozitia $i+2$ (aceasta trebuie sa fie libera).
* In saltul la stanga jetonul de pe pozitia $i$ sare peste jetonul de pe pozitia $i-1$ ; jetonul de pe pozitia $i-1$ este eliminat; jetonul de pe pozitia $i$ ajunge pe pozitia $i-2$ (aceasta trebuie sa fie libera).

De exemplu:

In configuratia $011$ sare la stanga jetonul de pe pozitia $3$ peste jetonul de pe pozitia $2$ si se obtine configuratia $100$.
In configuratia $110$ sare la dreapta jetonul de pe pozitia $1$ peste jetonul de pe pozitia $2$ si se obtine configuratia $001$.

 
* In configuratia $011$ sare la stanga jetonul de pe pozitia $3$ peste jetonul de pe pozitia $2$ si se obtine configuratia $100$.
* In configuratia $110$ sare la dreapta jetonul de pe pozitia $1$ peste jetonul de pe pozitia $2$ si se obtine configuratia $001$.

Jocul se termina cu succes atunci cand pe tabla ramane un singur jeton.

h2. Restrictii

* $1 ≤ T ≤ 10$
* $1 ≤ Lungimea oricarei configuratii ≤ 150 000$

* {$1 ≤ T ≤ 10$}
* {$1 ≤ Lungimea oricarei configuratii ≤ 150 000$}

h2. Exemplu

h3. Explicatie

Configuratia 1: jocul se termina cu succes in 0 mutari.
Configuratia 110: jocul se termina cu succes intr-o singura mutare (primul jeton sare peste cel de al doilea)
Configuratia 001111010: jocul se termina cu succes in 4 mutari
001111010->001100110->000010110->000011000->000100000

# Jocul se termina cu succes in {$0$} mutari.
# Jocul se termina cu succes intr-o singura mutare (primul jeton sare peste cel de al doilea).
# Jocul se termina cu succes in {$4$} mutari: {$001111010->001100110->000010110->000011000->000100000$}

== include(page="template/taskfooter" task_id="peg") ==

3134