Двочасткова гра

Limits: 2 sec., 256 MiB

Дано двочастковий граф, Зеник і Марічка грають у гру на ньому. За один хід можна провести ребро, так щоб граф надалі лишався двочастковим. Хто не зможе зробити хід — програє. Хто виграє при правильній грі обох суперників, якщо Марічка починає?

Зверніть увагу, що граф не може містити мультиребер в жоден момент часу.

Input

У першому рядку задано єдине ціле число \(t\) — кількість тестів, які потрібно розв’язати.

Далі йде опис кожного тесту, у першому рядку два цілі числа через пробіл — \(n\) та \(m\).

У наступних \(m\) рядках задано по два цілі числа \(u\) та \(v\) — ребра графу.

Output

Для кожного тесту виведіть єдиний рядок Marichka, якщо виграє Марічка, та Zenyk в іншому випадку.

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\),

заданий граф гарантовано двочастковий,

cума m по всіх тестах не перевищує \(10^6\).

Samples