P17128 [ICPC 2025 Shanghai R] AGI

Dr. Menji is an expert in AI. Now, he is training Bot, an AGI (Artificial Game Intelligence). To teach Bot how to play games, he plays with Bot every day. Today they are playing the following game: The game starts with a sequence of $2n$ non-negative integers, $a_1, a_2, \cdots, a_{2n}$, and a number $S$. Initially, $S = 0$. Menji and Bot take turns; Menji goes first: - In Menji’s turn, he chooses a number $x$ from the sequence, sets $S \leftarrow S \oplus x$, and deletes $x$ from the sequence. Note that $\oplus$ is the bitwise XOR (exclusive or) function. - In Bot’s turn, he chooses a number $x$ from the sequence and deletes $x$ from the sequence. The game ends when no numbers remain in the sequence. Menji wins if and only if $S = 0$ in the end; otherwise, Bot wins. Menji wonders if both players play optimally, who is the winner of the game.

The input contains multiple testcases. The first line contains an integer $T$ ($1 \le T \le 10^5$), the number of testcases. For each testcase, the first line contains an integer $n$ ($1 \le n \le 10^5$), described in the statement. The second line contains $2n$ integers $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), representing integers in the game. It’s guaranteed that the sum of $n$ over all testcases does not exceed $2 \times 10^5$.

For each testcase, if Menji can win the game, print `Menji` in one line; otherwise, print `Bot` in one line.

For the $1$st testcase, no matter what number Menji chooses, Bot can always choose a same number, so Menji always chooses a $1$ and a $3$, $S = 1 \oplus 3 = 2 \ne 0$, so Bot can always win. For the $2$nd testcase, Menji can choose a $1$ in the first turn; no matter what Bot chooses, Menji can choose another $1$, so Menji always receives two $1$s, $S = 1 \oplus 1 = 0$, so Menji can always win.