Dr. Menji er en ekspert på AI. Nå trener han Bot, en AGI (Artificial Game Intelligence).
For å lære Bot hvordan man spiller spill, spiller han med Bot hver dag. I dag spiller de følgende spill:
Spillet starter med en følge av $2n$ ikke-negative heltall, $a_1, a_2, \cdots, a_{2n}$, og et tall $S$. Til å begynne med er $S = 0$.
Menji og Bot bytter på å trekke; Menji starter:
- I Menjis tur velger han et tall $x$ fra følgen, setter $S \leftarrow S \oplus x$, og sletter $x$ fra følgen. Merk at $\oplus$ er bitvis XOR-funksjonen (eksklusiv eller).
- I Bots tur velger han et tall $x$ fra følgen og sletter $x$ fra følgen.
Spillet slutter når det ikke er flere tall igjen i følgen. Menji vinner hvis og bare hvis $S = 0$ til slutt; ellers vinner Bot.
Menji lurer på hvem som vinner spillet dersom begge spillerne spiller optimalt.
Inndata
Inndataene inneholder flere testtilfeller. Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^5$), antallet testtilfeller.
For hvert testtilfelle inneholder den første linjen et heltall $n$ ($1 \le n \le 10^5$), som beskrevet i oppgaveteksten.
Den andre linjen inneholder $2n$ heltall $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), som representerer heltallene i spillet.
Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $2 \times 10^5$.
Utdata
For hvert testtilfelle, hvis Menji kan vinne spillet, skriv ut Menji på én linje; ellers, skriv ut Bot på én linje.
Eksempel
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
Merk
For det første testtilfellet kan Bot, uansett hvilket tall Menji velger, alltid velge et likt tall, slik at Menji alltid velger én $1$-er og én $3$-er, $S = 1 \oplus 3 = 2 \neq 0$, så Bot kan alltid vinne.
For det andre testtilfellet kan Menji velge én $1$-er i første trekk; uansett hva Bot velger, kan Menji velge en annen $1$-er, slik at Menji alltid får to $1$-ere, $S = 1 \oplus 1 = 0$, så Menji kan alltid vinne.