Dr. Menji ist ein KI-Experte. Derzeit trainiert er Bot, eine AGI (Artificial Game Intelligence).
Um Bot beizubringen, wie man Spiele spielt, spielt er jeden Tag mit Bot. Heute spielen sie das folgende Spiel:
Das Spiel beginnt mit einer Folge von $2n$ nichtnegativen ganzen Zahlen, $a_1, a_2, \cdots, a_{2n}$, und einer Zahl $S$. Zu Beginn gilt $S = 0$.
Menji und Bot sind abwechselnd am Zug; Menji beginnt:
- In Menjis Zug wählt er eine Zahl $x$ aus der Folge, setzt $S \leftarrow S \oplus x$ und löscht $x$ aus der Folge. Beachte, dass $\oplus$ die bitweise XOR-Funktion (Exklusiv-Oder) ist.
- In Bots Zug wählt er eine Zahl $x$ aus der Folge und löscht $x$ aus der Folge.
Das Spiel endet, wenn keine Zahlen mehr in der Folge übrig sind. Menji gewinnt genau dann, wenn am Ende $S = 0$ gilt; andernfalls gewinnt Bot.
Menji fragt sich, wer das Spiel gewinnt, wenn beide Spieler optimal spielen.
Eingabe
Die Eingabe enthält mehrere Testfälle. Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^5$), die Anzahl der Testfälle.
Für jeden Testfall enthält die erste Zeile eine ganze Zahl $n$ ($1 \le n \le 10^5$), wie in der Aufgabenstellung beschrieben.
Die zweite Zeile enthält $2n$ ganze Zahlen $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), welche die ganzen Zahlen im Spiel darstellen.
Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet.
Ausgabe
Gib für jeden Testfall in einer Zeile Menji aus, falls Menji das Spiel gewinnen kann; andernfalls gib in einer Zeile Bot aus.
Beispiel
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
Hinweis
Für den ersten Testfall kann Bot unabhängig davon, welche Zahl Menji wählt, immer dieselbe Zahl wählen, sodass Menji immer eine $1$ und eine $3$ wählt, $S = 1 \oplus 3 = 2 \neq 0$, weshalb Bot immer gewinnen kann.
Für den zweiten Testfall kann Menji im ersten Zug eine $1$ wählen; unabhängig davon, was Bot wählt, kann Menji eine weitere $1$ wählen, sodass Menji immer zwei $1$en erhält, $S = 1 \oplus 1 = 0$, weshalb Menji immer gewinnen kann.