Fișierul intrare/ieșire	sir1.in, sir1.out	Sursă	Cupa Martisor 2013
Autor	clasică	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.5 sec	Limită de memorie	5120 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Sir1 (clasa a 8-a)

Roboții Eva și Wall-e joacă următorul joc: avînd un șir de n numere întregi, jucătorii aleg, pe rând, câte un număr de la începutul sau sfârșitul șirului de pe tablă, eliminîndu-l din șir. Jocul se termină atunci cînd ultimul număr a fost ridicat de pe tablă. Jocul este cîștigat de robotul care are suma numerelor alese cea mai mare. În caz de egalitate cîștigă Eva. Eva mută întotdeauna prima.

Cerință

Să se afle cine cîștigă jocul. Atunci cînd cîștigă Eva se va afișa 1, altfel se va afișa 2.

Date de intrare

Fișierul de intrare sir1.in va conține pe prima linie un număr T, numărul de teste din fișier. Pe următoarele T linii vom avea descrierea cîte unui joc, astfel: primul întreg din linie este n, numărul de elemente ale șirului, iar următorii n întregi sînt cele n numere din șirul inițial (la începutul acelui joc).

Date de ieșire

În fișierul de ieșire sir1.out se vor scrie T linii. Pe linia i vom afișa cîștigătorul jocului i, cu convenția de mai sus.

Restricții

• 1 ≤ T ≤ 10
• 1 ≤ n ≤ 1000
• -1.000.000 ≤ sir[i] ≤ 1.000.000 (elementele șirului)
• Eva mută prima
• Dacă Eva și Wall-e au același scor, Eva cîștigă

Exemplu