Tohtori Menji on tekoälyasiantuntija. Nyt hän kouluttaa Botia, joka on AGI (Artificial Game Intelligence).
Opettaakseen Botia pelaamaan pelejä hän pelaa Botin kanssa joka päivä. Tänään he pelaavat seuraavaa peliä:
Peli alkaa jonolla, jossa on $2n$ ei-negatiivista kokonaislukua, $a_1, a_2, \cdots, a_{2n}$, sekä luvulla $S$. Aluksi $S = 0$.
Menji ja Bot toimivat vuorotellen; Menji aloittaa:
- Menjin vuorolla hän valitsee jonosta luvun $x$, asettaa $S \leftarrow S \oplus x$ ja poistaa luvun $x$ jonosta. Huomaa, että $\oplus$ on bittikohtainen XOR-funktio (poissulkeva tai).
- Botin vuorolla hän valitsee jonosta luvun $x$ ja poistaa luvun $x$ jonosta.
Peli päättyy, kun jonossa ei ole enää yhtään lukua jäljellä. Menji voittaa jos ja vain jos lopussa $S = 0$; muussa tapauksessa Bot voittaa.
Menji pohtii, kumpi voittaa pelin, jos molemmat pelaajat pelaavat optimaalisesti.
Syöte
Syöte sisältää useita testitapauksia. Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), testitapausten lukumäärän.
Jokaisessa testitapauksessa ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^5$), joka on kuvattu tehtävänannossa.
Toinen rivi sisältää $2n$ kokonaislukua $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), jotka kuvaavat pelin kokonaislukuja.
On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^5$.
Tuloste
Tulosta jokaista testitapausta kohden omalle rivilleen Menji, jos Menji voi voittaa pelin; muussa tapauksessa tulosta omalle rivilleen Bot.
Esimerkki
5
2
1 1 3 3
2
1 1 1 3
3
1 1 4 5 1 4
3
1 9 1 9 8 10
6
1 1 4 5 1 4 1 9 1 9 8 10
Bot
Menji
Menji
Menji
Bot
Huomautus
Ensimmäisessä testitapauksessa riippumatta siitä, minkä luvun Menji valitsee, Bot voi aina valita saman luvun, joten Menji valitsee aina yhden luvun $1$ ja yhden luvun $3$, jolloin $S = 1 \oplus 3 = 2 \neq 0$, joten Bot voi aina voittaa.
Toisessa testitapauksessa Menji voi valita luvun $1$ ensimmäisellä vuorolla; riippumatta siitä, mitä Bot valitsee, Menji voi valita toisen luvun $1$, joten Menji saa aina kaksi lukua $1$, jolloin $S = 1 \oplus 1 = 0$, joten Menji voi aina voittaa.