Read problems statements in Mandarin Chinese  and Russian. 

Today is Chef's birthday. His mom gifted him a truly lovable gift, a permutation of first N positive integers.

She placed the permutation on a very long table in front of Chef and left it for him to play with it. But as there was a lot of people coming and wishing him. It was interfering with his game which made him very angry and he banged the table very hard due to which K numbers from the permutation fell down and went missing.

Seeing her son's gift being spoilt, his mom became very sad. Chef didn't want his mom to be sad as he loves her the most. So to make her happy, he decided to play a game with her with the remaining N - K numbers on the table. Chef wants his mom to win all the games.

Chef and his mom play alternatively and optimally. In Xth move, a player can choose some numbers out of all the numbers available on the table such that chosen numbers sum up to X. After the move, Chosen numbers are placed back on the table.The player who is not able to make a move loses.

Now, Chef has to decide who should move first so that his Mom wins the game.

As Chef is a small child, he needs your help to decide who should move first. Please help him, he has promised to share his birthday cake with you :)

------ Input ------ 

First Line of input contains a single integer T denoting the number of test cases.  
First line of each test case contains two space separated integers N and K denoting the size of
permutation and number of numbers fall down from the table. 
Next line of each test case contains K space separated integers denoting the values of missing numbers.

------ Output ------ 

For each test case, print "Chef" if chef should move first otherwise print "Mom" (without quotes).

------ Constraints ------ 
 
1 ≤ T ≤ 10^{5}, 1 ≤ N ≤ 10^{9}
0 ≤ K ≤ min(10^{5}, N)
All K numbers are distinct.
Value of each of K number belongs to [1,N].
Sum of K over all the test cases does not exceed 5*10^{5}.

------ Scoring ------ 

Subtask 1 (13 pts): 1  ≤  T  ≤  100, 1  ≤  N  ≤   10^{2}, 1  ≤  K < N. 
Subtask 2 (17 pts): 1  ≤  T  ≤  100, 1  ≤  N  ≤   10^{5}, K = 0. 
Subtask 3 (70 pts): Original Constraints. 

----- Sample Input 1 ------ 
2
5 2
3 5
5 1
1
----- Sample Output 1 ------ 
Mom
Chef
----- explanation 1 ------ 
For test case 1.
Mom can choose {1} to make 1.
Chef can choose {2} to make 2.
Mom can choose {1,2} to make 3.
Chef can choose {4} to make 4.
Mom can choose {1,4} to make 5.
Chef can choose {2,4} to make 6.
Mom can choose {1,2,4} to make 7.
Chef cannot make 8 out of the numbers on the table.

So,Chef loses and Mom wins.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Mathematics


Solutions:
def nsum(a, b):
	n1 = b * (b - 1) // 2 - a * (a + 1) // 2
	return n1
test = int(input())
for it in range(test):
	broken = False
	brokenAt = None
	tolook = 0
	(n, k) = [int(x) for x in input().strip().split()]
	if k != 0:
		lost = [int(x) for x in input().strip().split()]
		lost.sort()
		if lost[0] in (1, 2):
			tolook = lost[0]
		elif k == 1:
			tolook = 1 + n * (n + 1) // 2 - lost[0]
		else:
			tolook = nsum(0, lost[0])
			for i in range(k - 1):
				if lost[i] > tolook:
					tolook += 1
					broken = True
					brokenAt = i
					break
				else:
					tolook += nsum(lost[i], lost[i + 1])
			if not broken:
				if lost[-1] > tolook:
					tolook += 1
				else:
					tolook += 1 + nsum(lost[-1], n + 1)
	else:
		tolook = 1 + n * (n + 1) // 2
	if tolook % 2:
		print('Chef')
	else:
		print('Mom')


def main():
	from sys import stdin
	input()
	read = stdin.readline
	for x in stdin:
		(N, K) = map(int, x.split())
		if K:
			B = [int(i) for i in read().split()]
			B.append(N + 1)
			B.sort()
			ans = B[0] * (B[0] - 1) // 2
			for i in range(1, K + 1):
				if B[i - 1] > ans:
					break
				ans += (B[i] * (B[i] - 1) - B[i - 1] * (B[i - 1] + 1)) // 2
		else:
			ans = N * (N + 1) // 2
		print('Mom' if ans % 2 else 'Chef')
main()


A = []

def series(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k != 0:
		A = list(map(int, input().split()))
	A.append(n + 1)
	A.sort()
	(s, i) = (0, 0)
	if k == 0:
		s = series(n)
	else:
		for i in range(0, k + 1):
			if i == 0:
				s = series(A[i] - 1)
			else:
				s += max(0, series(A[i] - 1) - series(A[i - 1]))
			if s < A[i]:
				break
	print('Chef') if s % 2 == 0 else print('Mom')