Dr. Menji er sérfræðingur í gervigreind. Núna er hann að þjálfa Bot, sem er AGI (Artificial Game Intelligence).
Til að kenna Bot hvernig á að spila leiki spilar hann við Bot á hverjum degi. Í dag eru þeir að spila eftirfarandi leik:
Leikurinn byrjar með runu af $2n$ ekki-neikvæðum heiltölum, $a_1, a_2, \cdots, a_{2n}$, og tölu $S$. Í upphafi er $S = 0$.
Menji og Bot skiptast á að gera; Menji byrjar:
- Í umferð Menji velur hann tölu $x$ úr rununni, setur $S \leftarrow S \oplus x$ og eyðir $x$ úr rununni. Athugið að $\oplus$ er bitbundna XOR-fallið (annaðhvort eða).
- Í umferð Bot velur hann tölu $x$ úr rununni og eyðir $x$ úr rununni.
Leiknum lýkur þegar engar tölur eru eftir í rununni. Menji vinnur ef og aðeins ef $S = 0$ í lokin; annars vinnur Bot.
Menji veltir fyrir sér hver sé sigurvegari leiksins ef báðir leikmenn spila á besta mögulega hátt.
Inntak
Inntakið inniheldur mörg prófunartilvik. Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^5$), fjölda prófunartilvika.
Fyrir hvert prófunartilvik inniheldur fyrsta línan heiltölu $n$ ($1 \le n \le 10^5$), eins og lýst er í dæminu.
Önnur línan inniheldur $2n$ heiltölur $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), sem tákna heiltölurnar í leiknum.
Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^5$.
Úttak
Fyrir hvert prófunartilvik, ef Menji getur unnið leikinn, prentið Menji í eina línu; annars prentið Bot í eina línu.
Dæmi
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
Athugasemd
Fyrir fyrsta prófunartilvikið, sama hvaða tölu Menji velur, getur Bot alltaf valið sömu tölu, þannig að Menji velur alltaf einn $1$ og einn $3$, $S = 1 \oplus 3 = 2 \neq 0$, svo Bot getur alltaf unnið.
Fyrir annað prófunartilvikið getur Menji valið $1$ í fyrstu umferð; sama hvað Bot velur getur Menji valið annan $1$, þannig að Menji fær alltaf tvo $1$, $S = 1 \oplus 1 = 0$, svo Menji getur alltaf unnið.