Le Dr Menji est un expert en IA. En ce moment, il entraîne Bot, une AGI (Artificial Game Intelligence).
Pour apprendre à Bot à jouer à des jeux, il joue avec lui tous les jours. Aujourd'hui, ils jouent au jeu suivant :
Le jeu commence avec une suite de $2n$ entiers naturels, $a_1, a_2, \cdots, a_{2n}$, et un nombre $S$. Initialement, $S = 0$.
Menji et Bot jouent à tour de rôle ; Menji commence :
- Au tour de Menji, il choisit un nombre $x$ de la suite, affecte $S \leftarrow S \oplus x$, et supprime $x$ de la suite. Notez que $\oplus$ est la fonction OU exclusif bit à bit (XOR).
- Au tour de Bot, il choisit un nombre $x$ de la suite et supprime $x$ de la suite.
Le jeu se termine lorsqu'il ne reste plus aucun nombre dans la suite. Menji gagne si et seulement si $S = 0$ à la fin ; sinon, c'est Bot qui gagne.
Menji se demande qui sera le vainqueur du jeu si les deux joueurs jouent de manière optimale.
Entrée
L'entrée contient plusieurs cas de test. La première ligne contient un entier $T$ ($1 \le T \le 10^5$), le nombre de cas de test.
Pour chaque cas de test, la première ligne contient un entier $n$ ($1 \le n \le 10^5$), décrit dans l'énoncé.
La deuxième ligne contient $2n$ entiers $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), représentant les entiers du jeu.
Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $2 \times 10^5$.
Sortie
Pour chaque cas de test, si Menji peut gagner la partie, affichez Menji sur une ligne ; sinon, affichez Bot sur une ligne.
Exemple
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
Note
Pour le premier cas de test, quel que soit le nombre choisi par Menji, Bot peut toujours choisir le même nombre, de sorte que Menji choisit toujours un $1$ et un $3$, $S = 1 \oplus 3 = 2 \neq 0$, et Bot peut donc toujours gagner.
Pour le deuxième cas de test, Menji peut choisir un $1$ au premier tour ; quoi que Bot choisisse, Menji peut choisir un autre $1$, de sorte que Menji reçoit toujours deux $1$, $S = 1 \oplus 1 = 0$, et Menji peut donc toujours gagner.