* $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^$.

* Numărul de pietre din oricare grămadă este natural pozitiv mai mic sau egal cu $2 * 10^9^$.

h2. Exemplu

h2. Indicaţii de rezolvare

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 câştigătoare o configuraţie a grămezilor pentru care primul jucător are strategie sigură de câştig, respectiv stare necâştigatoare o configuraţie pentru care primul jucator va pierde. Se observă că stările câştigătoare corespund situaţiilor în 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 câştigătoare o configuraţie a grămezilor pentru care primul jucător are strategie sigură de câştig, respectiv stare necâştigătoare o configuraţie pentru care primul jucător va pierde. Se observă că stările câştigătoare corespund situaţiilor în care suma XOR a numerelor de pietre din grămezi este mai mare ca 0.

Pentru a demonstra acest lucru, următoarele condiţii sunt necesare si suficiente:

Pentru a demonstra acest lucru, următoarele condiţii sunt necesare şi suficiente:

# Dintr-o stare cu suma XOR 0, se poate ajunge doar în stări cu suma XOR pozitivă, sau jocul se termină. Scăzând din orice gramadă o cantitate pozitivă, evident vom schimba configuraţia binară a numărului de pietre cu cel puţin un bit, deci şi suma XOR. Jocul se termină cand toate grămezile au 0 pietre, deci şi suma XOR va fi 0.
# Dintr-o stare cu suma XOR pozitivă, se poate ajunge intr-o stare cu suma XOR 0. Căutăm o grămadă cu un număr X de pietre, care are un bit de 1 pe poziţia bitului cel mai semnificativ al sumei XOR, notată cu S. Din acea grămadă se vor scădea X - (X XOR S) pietre, (X XOR S) fiind mai mic decat X deoarece se anulează bitul cel mai semnificativ al lui S. Suma XOR rămasă după scădere este egală cu 0.

# Dintr-o stare cu suma XOR 0, se poate ajunge doar în stări cu suma XOR pozitivă, sau jocul se termină. Scăzând din orice grămadă o cantitate pozitivă, evident vom schimba configuraţia binară a numărului de pietre cu cel puţin un bit, deci şi suma XOR. Jocul se termină cand toate grămezile au 0 pietre, deci şi suma XOR va fi 0.
# Dintr-o stare cu suma XOR pozitivă, se poate ajunge într-o stare cu suma XOR 0. Căutăm o grămadă cu un număr X de pietre, care are un bit de 1 pe poziţia bitului cel mai semnificativ al sumei XOR, notată cu S. Din acea grămadă se vor scădea X - (X XOR S) pietre, (X XOR S) fiind mai mic decât X deoarece se anulează bitul cel mai semnificativ al lui S. Suma XOR rămasă după scădere este egală cu 0.

Pentru o demonstraţie mai pe larg şi alte variante de joc NIM, puteţi consulta acest 'articol':http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf