== include(page="template/taskheader" task_id="nim") ==

Se consideră $N$ grămezi de pietre. Doi jucători vor ridica alternativ oricâte pietre dintr-o singură grămadă. Câştigătorul este cel care ia ultima piatră.

Se consideră $n$ grămezi de pietre. Doi jucători vor ridica alternativ oricâte pietre dintr-o singură grămadă. Câştigătorul este cel care ia ultima piatră.

h2. Cerinta

h3. Cerinţă

Pentru T configuratii de joc date, sa se determine daca primul jucator are strategie sigura de castig.

Pentru $t$ configuraţii de joc date, să se determine dacă primul jucător are strategie sigură de câştig.

h2. Date de intrare

Fişierul de intrare $nim.in$ va contine pe prima linie numarul $T$ de jocuri. Pe urmatoarele $2*T$ linii se vor afla descrierile jocurilor, astfel: pe linia $2*i$ se va afla numarul $N{~i~}$ de gramezi ale jocului $i$, iar pe linia $2*i+1$ se vor afla ${N~i~}$ numere, reprezentand numarul de pietre din fiecare din cele $N{~i~}$ gramezi.

Fişierul de intrare $nim.in$ va conţine pe prima linie numărul $t$ de jocuri. Pe următoarele $2*t$ linii se vor afla descrierile jocurilor, astfel: pe linia $2*i$ se va afla numărul $n{~i~}$ de grămezi ale jocului $i$, iar pe linia $2*i+1$ se vor afla $n{~i~}$ numere, reprezentând numărul de pietre din grămezi.

h2. Date de ieşire

În fişierul de ieşire $nim.out$ se vor afisa $T$ linii, pe fiecare aflandu-se mesajul $"DA"$, daca jucatorul $1$ are strategie sigura de castig, respectiv $"NU"$, in caz contrar.

În fişierul de ieşire $nim.out$ se vor afişa $t$ linii, pe fiecare aflându-se mesajul $"DA"$, dacă jucătorul $1$ are strategie sigură de câştig, respectiv $"NU"$, în caz contrar.

h2. Restricţii

* $1 ≤ T ≤ 100$
* $1 ≤ N{~i~} ≤ 10 000$
* Numarul de pietre din oricare gramada este natural pozitiv mai mic sau egal cu $2 000 000 000$.

* $1 ≤ t ≤ 100$.
* $1 ≤ n{~i~} ≤ 10 000$.
* Numarul de pietre din oricare grămadă este natural pozitiv mai mic sau egal cu $2 * 10^9^$.

h2. Exemplu

DA
|

h2. Indicatii de rezolvare

h2. Indicaţii de rezolvare

Jocul impartial propus in aceasta problema se numeste 'NIM':http://en.wikipedia.org/wiki/Nim, stand la baza Teoriei Jocurilor. Numim stare castigatoare o configuratie a gramezilor pentru care primul jucator are strategie sigura de castig, respectiv stare necastigatoare o configuratie pentru care primul jucator va pierde. Se observa ca starile castigatoare corespund situatiilor in care suma XOR a numerelor de pietre din gramezi este mai mare ca 0.

Jocul imparţial propus în această problemă se numeşte 'jocul NIM':http://en.wikipedia.org/wiki/Nim, stând la baza teoriei jocurilor. Numim stare castigatoare o configuratie a gramezilor pentru care primul jucator are strategie sigura de castig, respectiv stare necastigatoare o configuratie pentru care primul jucator va pierde. Se observa ca starile castigatoare corespund situatiilor in care suma XOR a numerelor de pietre din gramezi este mai mare ca 0.

Pentru a demonstra acest lucru, urmatoarele conditii sunt necesare si suficiente: