Fişierul intrare/ieşire:	g.in, g.out	Sursă	Happy Coding 2008
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.375 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

G

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₁, respectiv G₂ pietre, astfel incat G₁+G₂=G, G₁>0 si G₂>0.
• daca G≥3, jucatorul poate lua o piatra din gramada, iar restul gramezii il poate imparti in doua gramezi continand G₁, respectiv G₂ pietre, astfel incat G₁+G₂=G-1, G₁>0 si G₂>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.

Date de intrare

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₁, ..., gp_N, separate prin cate un spatiu.

Date de iesire

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.

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].

Exemplu

Cum se trimit solutii?