There are N piles where the i^{th} pile consists of A_{i} stones.

Chef and Chefina are playing a game taking alternate turns with Chef starting first.  
In his/her turn, a player can choose any non-empty pile and remove exactly 1 stone from it. 

The game ends when exactly 1 pile becomes empty. The player who made the last move wins.  
Determine the winner if both players play optimally.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N denoting the number of piles.
- Next line contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} - denoting the number of stones in each pile.

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

For each test case, output CHEF if Chef wins the game, otherwise output CHEFINA.

Note that the output is case-insensitive i.e. CHEF, Chef, cHeF, and chef are all considered the same.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2
2 2
1
10
3
1 5 6

----- Sample Output 1 ------ 
CHEFINA
CHEFINA
CHEF

----- explanation 1 ------ 
Test Case $1$: No matter which stone Chef removes, Chefina will remove the remaining stone from the same pile and make it empty.

Test Case $2$: Since there is only $1$ pile containing $10$ stones, the game will last exactly $10$ moves with last move made by Chefina.

Test Case $3$: Chef can remove $1$ stone from the first pile and thus make it empty.

Difficulty: EASY
Tags: Game theory

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print('CHEF' if sum(a) % 2 or 1 in a else 'CHEFINA')


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	if 1 in A:
		print('CHEF')
	elif len(A) == 1 and A[0] % 2 == 0:
		print('CHEFINA')
	elif len(A) == 1 and A[0] % 2 != 0:
		print('CHEF')
	else:
		c = 0
		for j in A:
			c += j - 2
		if c % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in a:
		if i % 2 == 1:
			c += 1
	if 1 in a:
		print('CHEF')
	elif c % 2 == 1:
		print('CHEF')
	else:
		print('CHEFINA')


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % 2 != 0 or 1 in a:
		print('CHEF')
	else:
		print('CHEFINA')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if 1 in l:
		print('CHEF')
	elif sum(l) % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


for _ in range(int(input())):
	piles = int(input())
	pilelist = list(map(int, input().split()))
	if 1 in pilelist:
		print('CHEF')
	elif sum(pilelist) % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


for t in range(int(input())):
	n = int(input())
	stones = list(map(int, input().split(' ')))
	stones.sort()
	if 1 in stones:
		print('CHEF')
	elif sum(stones) % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


for r in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = sum(a)
	if 1 in a:
		print('CHEF')
	elif b & 1 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	l1 = sorted(l)
	for i in range(len(l1)):
		if l1[i] == 1:
			c = 1
			break
		else:
			c = c + l1[i] - 2
	if c % 2 == 0:
		print('CHEFINA')
	elif c % 2 == 1:
		print('CHEF')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if 1 in l:
		print('CHEF')
	else:
		sumi = 0
		l.sort()
		for i in l:
			if i > 2:
				sumi += i
		if sumi % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')


for t in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	if 1 in A:
		print('CHEF')
	else:
		A.sort()
		sum = 0
		for val in A:
			if val > 2:
				sum += val
		if sum % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')


t = int(input())
for i in range(t):
	n = int(input())
	abc = list(map(int, input().split()))
	for i in abc:
		if i == 1:
			print('CHEF')
			break
	else:
		if sum(abc) % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if a[0] == 1:
		print('CHEF')
	else:
		chef = 0
		chefina = 0
		for i in a:
			if i % 2 == 0:
				chefina += 1
			elif i % 2 != 0:
				chef += 1
		if chef % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	count = 0
	for x in l:
		if x > 2:
			count += x - 2
			x = 2
		l1.append(x)
	if 1 in l1:
		print('CHEF')
	elif count % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


T = int(input())
for _ in range(T):
	n = int(input())
	A = [int(x) - 2 for x in input().split()]
	if -1 in set(A):
		print('CHEF')
		continue
	if sum(A) % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


t = int(input())
for it in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for item in a:
		if item % 2 == 0:
			even.append(item)
		else:
			odd.append(item)
	if len(odd) == 0:
		print('CHEFINA')
	elif min(a) == 1:
		print('CHEF')
	elif sum(a) % 2 == 1:
		print('CHEF')
	else:
		print('CHEFINA')


from collections import Counter
for gagroz in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for i in a:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	oddSum = sum(odd)
	evenSum = sum(even)
	if 1 in odd:
		print('CHEF')
	elif len(odd) == 0:
		print('CHEFINA')
	elif (oddSum + evenSum) % 2 == 1:
		print('CHEF')
	else:
		print('CHEFINA')


for i in range(int(input())):
	a = int(input())
	lis = list(map(int, input().split()))
	if 1 in lis:
		print('CHEF')
	elif sum(lis) % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


t = int(input())
assert t >= 1 and t <= 1000
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	if 1 in arr:
		print('CHEF')
	elif sum(arr) % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	f = 0
	for i in range(n):
		if a[i] >= 2:
			c += a[i]
			if c % 2 == 0:
				f = 1
			else:
				f = 0
		else:
			f = 0
			break
	print('CHEFINA' if f == 1 else 'CHEF')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	flag = 0
	for i in range(n):
		if a[i] >= 2:
			cnt += a[i]
			if cnt % 2 == 0:
				flag = 1
			else:
				flag = 0
		else:
			flag = 0
			break
	if flag == 1:
		print('CHEFINA')
	else:
		print('CHEF')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sum(a)
	if 1 in a:
		print('CHEF')
	elif b % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	u = sum(a)
	if u % 2 == 0 and 1 not in a:
		print('CHEFINA')
	else:
		print('CHEF')


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))[:a]
	if 1 not in l:
		if sum(l) % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')
	else:
		print('CHEF')


t = int(input())
while t != 0:
	n = int(input())
	p = list(map(int, input().split()))
	if p.count(1) != 0:
		print('CHEF')
	else:
		s = 0
		for x in p:
			if x > 2:
				s += x - 2
		if s % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')
	t -= 1


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	turns = sum(a) - 2 * len(a)
	if min(a) == 1:
		print('CHEF')
	elif turns % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	mini = sum(A)
	if 1 in A:
		print('CHEF')
	elif mini % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(y) for y in input().split()]
	if 1 in l:
		print('CHEF')
	elif sum(l) % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if sum(l) % 2 == 1 or 1 in l:
		print('CHEF')
	else:
		print('CHEFINA')


for _ in range(int(input())):
	p = int(input())
	s = list(map(int, input().split()))
	s = s[0:p]
	m = min(s)
	if m == 1:
		print('CHEF')
	else:
		count = 0
		for i in range(len(s)):
			if s[i] % 2 == 1:
				count += 1
		if count % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')


a = int(input(''))
for i in range(a):
	x = int(input(''))
	t = [int(x) for x in input('').split()]
	if min(t) == 1:
		print('CHEF')
	else:
		c = 0
		for j in t:
			if j % 2 != 0:
				c = c + 1
		if c % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if min(arr) == 1:
		print('CHEF')
	else:
		c = 0
		for i in arr:
			if i % 2 == 1:
				c += 1
		if c % 2 == 1:
			print('CHEF')
		else:
			print('CHEFINA')


a = int(input())
for i in range(a):
	b = int(input())
	l = list(map(int, input().split()))
	if min(l) == 1:
		print('CHEF')
	else:
		count = 0
		for i in l:
			if i % 2 == 1:
				count = count + 1
		if count % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mi = min(l)
	if mi == 1:
		print('CHEF')
	else:
		count = 0
		for item in l:
			if item % 2 == 1:
				count += 1
		if count % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	if 1 in A:
		print('CHEF')
	elif s % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	u = min(a)
	if u == 1:
		print('CHEF')
	else:
		v = 0
		for j in a:
			if j % 2 == 1:
				v += 1
		if v % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')


for i in range(int(input())):
	N = int(input())
	list_a = [int(i) for i in input().split()]
	e = 0
	o = 0
	if sum(list_a) % 2 == 1 or 1 in list_a:
		print('CHEF')
	else:
		print('CHEFINA')


for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if n == 1 and a[0] % 2 == 0:
		print('CHEFINA')
	elif n == 1 and a[0] % 2 != 0:
		print('CHEF')
	elif 1 in a:
		print('CHEF')
	else:
		odd = 0
		eve = 0
		for i in a:
			if i % 2 == 0:
				eve += 1
			else:
				odd += 1
		if odd % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')