Bipartite Game

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Given a bipartite graph, Zenyk and Marichka are playing a game on it. In one turn, an edge can be added such that the graph remains bipartite. Whoever cannot make a move loses. Who wins under optimal play by both players, if Marichka starts?

Note that the graph cannot contain multi-edges at any point in time.

Input

The first line contains a single integer \(t\) — the number of test cases to solve.

Then follows the description of each test case. The first line contains two integers separated by a space — \(n\) and \(m\).

The next \(m\) lines each contain two integers \(u\) and \(v\) — the edges of the graph.

Output

For each test case, output a single line Marichka if Marichka wins, and Zenyk otherwise.

Constraints

\(1 \le t \le 10^4\),

\(1 \le n \le 10^5\),

\(0 \le m \le 10^5\),

\(1 \le u, v \le n\),

the given graph is guaranteed to be bipartite,

the sum of \(m\) over all test cases does not exceed \(10^6\).

Samples