== 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 $g{~i~}$ pietre. Cei doi jucatori efectueaza mutari alternativ, prima mutare fiind efectuata de jucatorul $1$. O mutare consta in alegerea unei gramezi avand $G$ 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 $G1$, respectiv $G2$ pietre, astfel incat $G1+G2=G$, $G1 > 0$ si $G2 > 0$.
* daca $G ≥ 3$, jucatorul poate lua o piatra din gramada, iar restul gramezii este impartit in doua gramezi continand $G1$, respectiv $G2$ pietre, astfel incat $G1+G2=G-1$, $G1 > 0$ si $G2 > 0$.
 
Jocul se termina cand nu s emai 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 $g{~1~}, ..., g{~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") ==