Zenyk and Marichka are playing a game taking turns alternatively. They have N piles of stones. In the i^{th} pile, there are A_{i} stones initially.

Marichka goes first, and removes any non-zero number of stones from any pile.
After that, in one move, a player can take any number of stones from any pile, but not less than the number of stones taken by the opponent in the previous move.

The player who cannot make a move loses. If both players play optimally, find the winner of the game.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.

• The first line of each tets case contains single integer N — the number of piles.

• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$ — the numbers of stones in piles initially.

------ Output Format ------

For each test case, output a new line containing:
- Marichka if Marichka wins.
- Zenyk if Zenyk wins.

Note that you may print each character in lowercase or uppercase. For example, the strings Zenyk, ZENYK, zenyk, and zEnYK are considered identical.

------ Constraints ------

$1 ≤T ≤10^{5}$
$1 ≤N ≤10^{5}$
$1 ≤A_{i} ≤10^{9}$
- Sum of $N$ over all test cases doesn't exceed $2 \cdot 10^{5}$

------ subtasks ------

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------
3
3
1 2 3
2
1 1
1
10

----- Sample Output 1 ------
Marichka
Zenyk
Marichka

----- explanation 1 ------
For the first testcase, Marichka can take $3$ stones from the last pile in the first move, then Zenyk won't be able to make a move, as each pile will contain less than $3$ stones.

见题面

见题面