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.

Difficulty: MEDIUM

Starter code:

Solutions:
from collections import Counter

def solve(arr):
	d = Counter(arr)
	f = True
	for val in d.values():
		if val & 1 == 1:
			f = False
	if f:
		return 'Zenyk'
	else:
		return 'Marichka'
T = int(input())
for i in range(T):
	n = int(input())
	if n == 1:
		print('Marichka')
	else:
		lis = list(map(int, input().split()))
		print(solve(lis))


from collections import Counter

def solve(arr):
	s = set(arr)
	n = len(arr)
	if len(s) == n:
		return 'Marichka'
	if len(s) == 1:
		if n & 1 == 0:
			return 'Zenyk'
		else:
			return 'Marichka'
	else:
		d = Counter(arr)
		for item in d.values():
			if item & 1 == 1:
				return 'Marichka'
		return 'Zenyk'
T = int(input())
for i in range(T):
	n = int(input())
	if n == 1:
		print('Marichka')
	else:
		lis = list(map(int, input().split()))
		print(solve(lis))


from collections import Counter
for _ in range(int(input())):
	s = int(input())
	p = Counter([int(x) for x in input().split()])
	res = 'Zenyk'
	for (k, l) in p.items():
		if l % 2:
			res = 'Marichka'
			break
	print(res)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = Counter([int(x) for x in input().split()])
	ans = 'Zenyk'
	for (x, y) in a.items():
		if y % 2:
			ans = 'Marichka'
			break
	print(ans)


for tc in range(int(input())):
	n = int(input())
	kmap = {}
	arr = list(map(int, input().split()))
	dagad = 0
	for ele in arr:
		dagad = max(dagad, ele)
		if ele not in kmap:
			kmap[ele] = 1
		else:
			kmap[ele] += 1
	if kmap[dagad] % 2 == 0 and len(kmap) == 1:
		print('Zenyk')
	elif kmap[dagad] % 2 == 1 and len(kmap) == 1:
		print('Marichka')
	else:
		win = False
		for key in kmap:
			if kmap[key] % 2 == 1:
				win = True
		print('Marichka' if win else 'Zenyk')


def fun(a):
	c = {}
	b = set(a)
	if len(b) == 1:
		if len(a) % 2 == 0:
			return 'Zenyk'
		else:
			return 'Marichka'
	elif len(b) == len(a):
		return 'Marichka'
	else:
		for i in a:
			if c.get(i) is None:
				c[i] = 1
			else:
				c[i] += 1
		for i in c.values():
			if i % 2 == 1:
				return 'Marichka'
		return 'Zenyk'
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(fun(a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = input().split(' ')
	d = {}
	for j in a:
		num = int(j)
		d[num] = d.get(num, 0) + 1
	for k in d:
		if d[k] % 2:
			print('Marichka')
			break
	else:
		print('Zenyk')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = 0
	c = Counter(arr)
	if len(c) == n:
		print('Marichka')
	else:
		for i in c.values():
			if i % 2 == 1:
				print('Marichka')
				flag = 1
				break
		if flag == 0:
			print('Zenyk')


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	assert len(a) == n
	cts = {}
	for x in a:
		cts[x] = cts.get(x, 0) + 1
	if any((c % 2 != 0 for c in cts.values())):
		print('Marichka')
	else:
		print('Zenyk')


t = int(input())
for i in range(t):
	n = int(input())
	mp = {}
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	for i in arr:
		mp.setdefault(i, 0)
		mp[i] += 1
	turn = 1
	for v in mp.values():
		if v % 2:
			turn = 0
			break
	if turn:
		print('Zenyk')
	else:
		print('Marichka')


for _ in range(int(input())):
	n = int(input())
	pile = list(map(int, input().split(' ')))
	m = {}
	for i in pile:
		m[i] = m.get(i, 0) + 1
	ans = None
	for v in m.values():
		if v % 2 == 1:
			ans = 'Marichka'
			break
	print(ans) if ans else print('Zenyk')


t = int(input())
for i in range(t):
	n = int(input())
	piles = [int(el) for el in input().split()]
	piles.sort()
	current = piles[0]
	count = 1
	odd_found = False
	for j in range(1, n):
		if piles[j] == current:
			count += 1
		else:
			if count % 2 == 1:
				odd_found = True
				break
			current = piles[j]
			count = 1
	odd_found = odd_found or count % 2 == 1
	if odd_found:
		print('Marichka')
	else:
		print('Zenyk')


def pf(l):
	c = {}
	s = set(l)
	if len(s) == 1:
		if len(l) % 2 == 0:
			return 'Zenyk'
		else:
			return 'Marichka'
	elif len(s) == len(l):
		return 'Marichka'
	else:
		for i in l:
			if c.get(i) is None:
				c[i] = 1
			else:
				c[i] += 1
		for i in c.values():
			if i % 2 == 1:
				return 'Marichka'
		return 'Zenyk'
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(pf(l))


for _ in range(int(input())):
	n = int(input())
	arr = sorted([int(i) for i in input().split()])
	counts = {}
	for i in arr:
		counts[i] = counts.get(i, 0) + 1
	num_counts = list(counts.values())
	flag = 0
	for i in num_counts:
		if i % 2 != 0:
			flag = 1
	if flag == 1:
		print('Marichka')
	else:
		print('Zenyk')


for _ in range(int(input())):
	n = int(input())
	arr = sorted([int(i) for i in input().split()])
	counts = {}
	for i in arr:
		counts[i] = counts.get(i, 0) + 1
	nums = list(counts.keys())
	num_counts = list(counts.values())
	zipped = sorted(zip(nums, num_counts), reverse=True)
	if zipped[0][1] % 2 != 0:
		print('Marichka')
	elif len(zipped) == 1:
		print('Zenyk')
	else:
		flag = 0
		for (num, its_count) in zipped:
			if its_count % 2 != 0:
				flag = 1
		if flag == 0:
			print('Zenyk')
		else:
			print('Marichka')


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	d = {}
	for i in A:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for i in d.values():
		if i % 2 != 0:
			print('Marichka')
			break
	else:
		print('Zenyk')


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	freq = {}
	ans = 'Zenyk'
	for i in arr:
		if i in freq:
			freq[i] += 1
		else:
			freq[i] = 1
	for i in freq:
		if freq[i] % 2 != 0:
			ans = 'Marichka'
			break
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = map(int, input().split())
	d = {}
	for i in a:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for i in d.values():
		if i % 2 != 0:
			print('Marichka')
			break
	else:
		print('Zenyk')


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = Counter(l)
	if d[max(d.values())] % 2 == 1:
		print('Marichka')
	else:
		t = list(d.keys())
		t.sort(reverse=True)
		for i in t:
			if d[i] % 2 == 1:
				print('Marichka')
				break
		else:
			print('Zenyk')


n = int(input())
while n:
	x = int(input())
	y = list(map(int, input().split()))
	hmap = {}
	for item in y:
		if hmap.get(item) == None:
			hmap[item] = 1
		else:
			hmap[item] += 1
	flag = 'z'
	for key in hmap.keys():
		if hmap[key] % 2 == 1:
			print('Marichka')
			flag = 'm'
			break
	if flag == 'z':
		print('Zenyk')
	n -= 1


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	c = 0
	for j in d.values():
		if j % 2 == 1:
			c += 1
	if c > 0:
		print('Marichka')
	else:
		print('Zenyk')


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print('Marichka')
	else:
		d = {}
		for i in range(n):
			d[a[i]] = d.get(a[i], 0) + 1
		v = list(zip(d.keys(), d.values()))
		v.sort(reverse=True)
		f = 0
		for i in v:
			if i[1] % 2 != 0:
				print('Marichka')
				f = 1
				break
		if f == 0:
			print('Zenyk')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	h = {}
	for i in l:
		if i in h:
			h[i] += 1
		else:
			h[i] = 1
	flag = 1
	for i in h.values():
		if i % 2 != 0:
			flag = 0
			break
		else:
			flag = 1
	print('Marichka' if flag == 0 else 'Zenyk')


def f():
	n = int(input())
	a = map(int, input().split())
	d = {}
	for i in a:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for i in d.values():
		if i % 2 != 0:
			return 'Marichka'
	return 'Zenyk'
for _ in range(int(input())):
	print(f())


from collections import Counter

def sol(n, a):
	d = Counter(a)
	c = False
	for i in d:
		if d[i] % 2 != 0:
			c = True
			return 'Marichka'
	if c == False:
		return 'Zenyk'
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(sol(n, a))


for test_case in range(int(input())):
	length = int(input())
	list_a = list(map(int, input().split()))
	dict_a = {}
	for i in list_a:
		if i not in dict_a:
			dict_a[i] = 1
		else:
			dict_a[i] += 1
	flag = 0
	for value in dict_a.values():
		if value % 2 != 0:
			print('Marichka')
			flag = 1
			break
	if flag == 0:
		print('Zenyk')


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	print('Marichka' if any((i % 2 != 0 for i in d.values())) else 'Zenyk')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	c = 0
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		d[i] += 1
	for value in d.values():
		if value % 2 == 0:
			c = 1
			break
	if c == 0:
		print('Zenyk')
	else:
		print('Marichka')


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	d = {}
	for i in lst:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for j in d.values():
		if j % 2 == 1:
			print('Marichka')
			break
	else:
		print('Zenyk')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = {}
	for j in a:
		if j not in b:
			b[j] = 1
		else:
			b[j] += 1
	for j in b.values():
		if j & 1:
			print('Marichka')
			break
	else:
		print('Zenyk')


for t in range(int(input())):
	input()
	ai = [int(i) for i in input().split()]
	m = {}
	for i in ai:
		if i in m:
			m[i] += 1
		else:
			m[i] = 1
	for i in m.keys():
		if m[i] % 2 == 1:
			print('Marichka')
			break
	else:
		print('Zenyk')


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = Counter(l)
	for i in k.values():
		if i % 2 != 0:
			print('Marichka')
			break
	else:
		print('Zenyk')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	for i in c.values():
		if i % 2 != 0:
			print('Marichka')
			break
	else:
		print('Zenyk')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for j in l:
		if j in d:
			d[j] += 1
		else:
			d[j] = 1
		m = j
	for j in d:
		if d[j] % 2 == 1:
			print('Marichka')
			break
	else:
		print('Zenyk')


for i in range(int(input())):
	x = int(input())
	l = [int(i) for i in input().split()]
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for m in d:
		if d[m] % 2 == 1:
			print('Marichka')
			break
	else:
		print('Zenyk')


from collections import Counter
numTest = int(input())
for _ in range(numTest):
	n = int(input())
	arr = Counter(map(int, input().split()))
	for i in arr:
		if arr[i] % 2 != 0:
			print('Marichka')
			break
	else:
		print('Zenyk')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mx = max(arr)
	count = Counter(arr)
	ans = 0
	for i in count:
		if count[i] % 2 != 0:
			print('Marichka')
			ans = 1
			break
	if ans == 0:
		print('Zenyk')


testcases = int(input())
for eachcase in range(testcases):
	length = int(input())
	stones = list(map(int, input().split()))
	samepiles = {}
	for piles in stones:
		samepiles[piles] = 1 + samepiles.get(piles, 0)
	ans = 'Zenyk'
	for piles in samepiles:
		if samepiles[piles] & 1:
			ans = 'Marichka'
			break
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	i = 0
	x = len(a)
	if x % 2 != 0:
		print('Marichka')
	else:
		while i < x:
			if a[x - 1 - i] > a[x - 2 - i]:
				print('Marichka')
				break
			if i == x - 2 and a[0] == a[1]:
				print('Zenyk')
			i = i + 2


p = int(input())
for i in range(p):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	lst.reverse()
	freq = []
	s = 1
	flag = 0
	for i in range(1, n):
		if lst[i] == lst[i - 1]:
			s += 1
			flag = 1
		else:
			freq.append(s)
			s = 1
	freq.append(s)
	ans = ''
	for i in range(len(freq)):
		if freq[i] % 2 != 0:
			ans = 'Marichka'
	if ans:
		print(ans)
	else:
		print('Zenyk')


from collections import Counter
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	for k in sorted(c.keys(), reverse=True):
		if c[k] & 1:
			print('Marichka')
			break
	else:
		print('Zenyk')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ct = {}
	for x in a:
		ct[x] = ct.get(x, 0) + 1
	if any((c % 2 != 0 for c in ct.values())):
		print('Marichka')
	else:
		print('Zenyk')


t = int(input())
for i in range(t):
	n = int(input())
	d = {}
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	for i in arr:
		d.setdefault(i, 0)
		d[i] += 1
	temp = 1
	for i in d.values():
		if i % 2:
			temp = 0
			break
	if temp:
		print('Zenyk')
	else:
		print('Marichka')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print('Marichka')
	else:
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		flag = 0
		for i in d:
			if d[i] % 2 != 0:
				flag = 1
				break
		if flag:
			print('Marichka')
		else:
			print('Zenyk')


from collections import Counter
from math import ceil

def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	N = int(input())
	arr = inparr()
	d1 = Counter(arr)
	ok = True
	for i in d1:
		if d1[i] % 2:
			ok = False
			break
	if ok:
		print('Zenyk')
	else:
		print('Marichka')


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	b.sort()
	for f in range(len(b)):
		if b[a - 1] != b[a - 2] or a == 1:
			print('Marichka')
			break
		elif b[a - 1] == b[a - 2]:
			a = a - 2
			if a == 0:
				print('Zenyk')
				break


from collections import Counter
T = int(input())
for tc in range(T):
	n = int(input())
	l = list(map(int, input().split(' ')))
	m = ''
	z = 'Zenyk'
	d = dict(Counter(l))
	flag = 1
	for i in d.values():
		if i % 2 == 0:
			flag = 1
		else:
			flag = 0
			break
	if flag == 1:
		print('Zenyk')
	else:
		print('Marichka')


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	big = 0
	bigc = 1
	l = list(map(int, input().split()))
	l.sort()
	pre = l[0]
	for i in range(1, len(l)):
		if pre != l[i]:
			pre = l[i]
			if bigc & 1:
				big = 1
			bigc = 1
		else:
			bigc += 1
	if bigc & 1:
		big = 1
	if big == 1:
		print('Marichka')
	else:
		print('Zenyk')


for e in range(int(input())):
	n = int(input())
	a = list(map(str, input().split()))
	a.sort(reverse=True)
	cts = {}
	for x in a:
		cts[x] = cts.get(x, 0) + 1
	k = 0
	for x in cts:
		if cts[x] % 2 != 0:
			print('Marichka')
			k = 1
			break
	if k == 0:
		print('Zenyk')


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	m = max(l)
	d = Counter(l)
	c = 0
	for i in d:
		if d[i] % 2 != 0:
			print('Marichka')
			c = 1
			break
	if c == 0:
		print('Zenyk')


for i in range(int(input())):
	k = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	c = 0
	for j in d:
		if d[j] % 2 == 0:
			c += 1
	if c != len(d):
		print('Marichka')
	else:
		print('Zenyk')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	count = {}
	for x in arr:
		if x in count:
			count[x] += 1
		else:
			count[x] = 1
	for x in count.values():
		if x % 2 == 1:
			print('Marichka')
			break
	else:
		print('Zenyk')


from collections import Counter

def test():
	n = int(input())
	a = list(map(int, input().split()))
	d = Counter(a)
	for i in d:
		if d[i] % 2:
			return 'Marichka'
	return 'Zenyk'
	print(b)
t = int(input())
for _ in range(t):
	print(test())


for n in range(int(input())):
	s = int(input())
	arr = input().split()
	if s == 1:
		print('Marichka')
	else:
		dt = {}
		for i in arr:
			if i in dt:
				dt[i] += 1
			else:
				dt[i] = 1
		dar = []
		for i in dt:
			dar.append({i: dt[i]})
		if len(dar) == 1:
			p = dar[0]
			key = [*p]
			if dar[0][key[0]] % 2 == 1:
				print('Marichka')
			else:
				print('Zenyk')
		else:
			for i in range(len(dar) - 2, -1, -1):
				z = [*dar[i]]
				y = [*dar[i + 1]]
				dar[i][z[0]] += dar[i + 1][y[0]]
				ans = 0
			for i in range(len(dar) - 1, -1, -1):
				q = [*dar[i]]
				if dar[i][q[0]] % 2 == 1:
					ans = 1
					break
			if ans == 1:
				print('Marichka')
			else:
				print('Zenyk')


import collections

def solve(dic):
	for d in dic:
		if dic[d] % 2:
			return 'Marichka'
	return 'Zenyk'
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a_Freq = collections.Counter(a)
	print(solve(a_Freq))


class Solution:

	def TakeNotLess(self, arr):
		arr.sort(reverse=True)
		(n, win) = (len(arr), 'Marichka')
		for i in range(0, n - 1, 2):
			if arr[i] != arr[i + 1]:
				win = 'Marichka'
				break
			else:
				win = 'Zenyk'
		print(win)
s = Solution()
T = int(input())
for i in range(T):
	N = int(input())
	pile = list(map(int, input().split()))
	s.TakeNotLess(pile)


case = int(input())
for _ in range(case):
	n = int(input())
	A = list(map(int, input().split(' ')))
	cm = max(A)
	instance = {}
	for value in A:
		if value not in instance:
			instance[value] = 0
		instance[value] += 1
	if instance[cm] & 1 == 1:
		print('Marichka')
	else:
		M = False
		for key in instance:
			if instance[key] & 1 == 1:
				M = True
				break
		if M:
			print('Marichka')
		else:
			print('Zenyk')


T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	win = 'Marichka'
	for i in range(0, n - 1, 2):
		if arr[i] != arr[i + 1]:
			win = 'Marichka'
			break
		else:
			win = 'Zenyk'
	print(win)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ca = Counter(a)
	v = ca.values()
	ans = 'Zenyk'
	for i in v:
		if i % 2 == 1:
			ans = 'Marichka'
			break
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l.reverse()
	winner = 'Marichka'
	for j in range(0, n - 1, 2):
		if l[j] != l[j + 1]:
			winner = 'Marichka'
			break
		else:
			winner = 'Zenyk'
	print(winner)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = max(l)
	b = l.count(a)
	d = {}
	for j in l:
		try:
			d[j] += 1
		except:
			d[j] = 1
	flag = False
	for v in d.values():
		if v % 2 != 0:
			flag = True
	if flag or b % 2 != 0:
		print('Marichka')
	else:
		print('Zenyk')