== include(page="template/taskheader" task_id="g") ==
Poveste si cerinta...
Doi jucatori (numerotati $1$ si $2$) joaca urmatorul joc: Ei au la dispozitie $N$ gramezi, numerotate de la $1$ la $N$. Gramada $i$ contine $gp{~i~}$ pietre. Cei doi jucatori efectueaza mutari alternativ, prima mutare fiind efectuata de jucatorul $1$. O mutare consta in alegerea unei gramezi (avand $G>0$ pietre) si efectuarea uneia din urmatoarele actiuni:
* daca $G≥1$, jucatorul poate lua o piatra din gramada.
* daca $G≥2$, jucatorul poate imparti gramada in doua gramezi continand $G{~1~}$, respectiv $G{~2~}$ pietre, astfel incat $G{~1~}+G{~2~}=G$, $G{~1~}>0$ si $G{~2~}>0$.
* daca $G≥3$, jucatorul poate lua o piatra din gramada, iar restul gramezii il poate imparti in doua gramezi continand $G{~1~}$, respectiv $G{~2~}$ pietre, astfel incat $G{~1~}+G{~2~}=G-1$, $G{~1~}>0$ si $G{~2~}>0$.
Jocul se termina cand nu se mai poate efectua nicio mutare (toate gramezile sunt goale), iar jucatorul care a efectuat ultima mutare este castigatorul. Scrieti un program care determina care dintre cei doi jucatori are strategie sigura de castig.
h2. Date de intrare
Fisierul de intrare $g.in$ ...
Prima linie a fisierului de intrare $g.in$ contine numarul natural $T$, reprezentand numarul de teste descrise in fisier. Un test consta din doua linii: pe prima linie se afla numarul initial de gramezi $N$, iar pe a doua linie se afla numerele $gp{~1~}, ..., gp{~N~}$, separate prin cate un spatiu.
h2. Date de iesire
In fisierul de iesire $g.out$ ...
In fisierul de iesire $g.out$ veti afisa $T$ linii, cate una pentru fiecare test, in ordinea in care apar testele in fisierul de intrare. Pe fiecare linie se va gasi numarul $1$, daca jucatorul $1$ are strategie sigura de castig, respectiv $2$, daca cel de-al doilea jucator are strategie sigura de castig.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 16$
* $1 ≤ N ≤ 100.000$
* Numarul de pietre dintr-o gramada este un numar intreg din intervalul $[1, 2.100.000.000]$.
h2. Exemplu
table(example). |_. g.in |_. g.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
...
|5
1
1
1
2
1
3
3
1 2 3
4
1 3 2 4
|1
1
1
1
2|
== include(page="template/taskfooter" task_id="g") ==
