CSES - Nim-peli II
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Uolevi ja Maija pelaavat peliä, jossa on nn kasaa tikkuja, joissa on aluksi x1,x2,,xnx_1,x_2,\ldots,x_n tikkua. Jokaisella vuorolla pelaaja valitsee yhden pinoista ja poistaa siitä 11, 22 tai 33 tikkua. Pelin voittaja on se, joka poistaa viimeisen tikun.

Tehtäväsi on selvittää, kumpi pelaaja voittaa, kun Uolevi aloittaa pelin ja molemmat pelaavat optimaalisesti.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku tt: testien määrä. Sitten syötteessä on tt testitapauksen kuvaus:

Ensimmäisellä rivillä on kokonaisluku nn: kasojen määrä.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n: kunkin kasan tikkujen määrä.

Tuloste

Tulosta jokaisen testitapauksen vastaukseksi, kumpi pelaaja voittaa pelin.

Rajat

  • 1t10001 \le t \le 1000
  • 1n1051 \le n \le 10^5
  • 1xi1091 \le x_i \le 10^9
  • kaikkien lukujen nn summa on enintään 10510^5

Esimerkki

Syöte:

3
4
5 7 2 5
2
4 1
3
4 4 4

Tuloste:

Uolevi
Uolevi
Maija