Nim-peli II

• Time limit: 1.00 s
• Memory limit: 128 MB

Uolevi ja Maija pelaavat peliä, jossa on $n$ kasaa tikkuja, joissa on aluksi $x_1,x_2,\ldots,x_n$ tikkua. Jokaisella vuorolla pelaaja valitsee yhden pinoista ja poistaa siitä $1$, $2$ tai $3$ 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 $t$: testien määrä. Sitten syötteessä on $t$ testitapauksen kuvaus:

Ensimmäisellä rivillä on kokonaisluku $n$: kasojen määrä.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\ldots,x_n$: kunkin kasan tikkujen määrä.

Tuloste

Tulosta jokaisen testitapauksen vastaukseksi, kumpi pelaaja voittaa pelin.

Rajat

• $1 \le t \le 1000$
  
• $1 \le n \le 10^5$
  
• $1 \le x_i \le 10^9$
  
• kaikkien lukujen $n$ summa on enintään $10^5$
  

Esimerkki

Syöte:
3
4
5 7 2 5
2
4 1
3
4 4 4

Tuloste:
Uolevi
Uolevi
Maija