Chef and Chefina are playing a game. Chef plays first.

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

In his/her turn, a player can do one of the following:

Take any non-empty pile and remove 1 stone from it.
Take any pile containing atleast 2 stones and split it into two piles containing X and Y stones such that X+Y equals the initial number of stones in the chosen pile. Note that in this case, the number of piles increases by 1.

The player who cannot make a move loses. 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 initial number of piles.
- The next line contains N space separated integers A_{1}, A_{2}, A_{3}, \dots, A_{N}, the number of stones initially in each pile.

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

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

You may print each character in uppercase or lowercase. For example, the strings CHEF, chef, Chef, and cHEf are all considered identical.

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

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

----- Sample Input 1 ------ 
3
2
3 3
5
2 1 1 1 1
3
2 2 2

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

----- explanation 1 ------ 
Test case $1$: Consider the following set of moves:
- Chef splits the first pile into two piles. Thus, after his move, the piles are $[1, 2, 3]$.
- Chefina takes a stone from the first pile. Thus, after her move, the piles are $[2, 3]$.
- Chef splits the first pile into two piles. Thus, after his move, the piles are $[1, 1, 3]$.
- Chefina takes a stone from the first pile. Thus, after her move, the piles are $[1, 3]$.
- Chef splits the second pile into two piles. Thus, after his move, the piles are $[1, 1, 2]$.
- Chefina takes a stone from the first pile. Thus, after her move, the piles are $[1, 2]$.
- Chef takes a stone from the first pile. Thus, after his move, the piles are $[2]$.
- Chefina splits the first pile into two piles. Thus, after her move, the piles are $[1, 1]$.
- Chef takes a stone from the first pile. Thus, after his move, the piles are $[1]$.
- Chefina takes a stone from the first pile. Thus, after her move, all piles are empty.

Since Chef has no valid move, he loses. Note that this might not be an optimal sequence of moves.

Test case $2$: Consider the following set of moves:
- Chef splits the first pile into two piles. Thus, after his move, the piles are $[1, 1, 1, 1, 1, 1]$.
- Chefina takes a stone from the first pile. Thus, after her move, the piles are $[1, 1, 1, 1, 1]$.
- Chef takes a stone from the first pile. Thus, after his move, the piles are $[1, 1, 1, 1]$.
- Chefina takes a stone from the first pile. Thus, after her move, the piles are $[1, 1, 1]$.
- Chef takes a stone from the first pile. Thus, after his move, the piles are $[1, 1]$.
- Chefina takes a stone from the first pile. Thus, after her move, the piles are $[1]$.
- Chef takes a stone from the first pile. Thus, after his move, all piles are empty.

Since Chefina has no valid move, she loses. Note that this might not be an optimal sequence of moves.

Difficulty: VERY_HARD
Tags: Game theory

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	l = input().split(' ')
	a = 0
	m = l.count('1')
	for j in l:
		x = int(j)
		if x != 1 and (not x % 2):
			a += 1
	if not m % 2 and (not a % 2):
		print('CHEFINA')
	else:
		print('CHEF')


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


def pile():
	return [int(x) for x in input().split()]
for _ in range(int(input())):
	n = int(input())
	a = pile()
	assert len(a) == n
	flip = 0
	for x in a:
		if x == 1:
			flip ^= 1
		else:
			flip ^= 2 * (1 - x % 2)
	print('CHEF' if flip != 0 else 'CHEFINA')


for r in range(int(input())):
	pile = int(input())
	stones = list(map(int, input().split()))
	one = even = 0
	for i in stones:
		if i == 1:
			one += 1
		elif i % 2 == 0:
			even += 1
	if one % 2 == 0 and even % 2 == 0:
		print('CHEFINA ')
	else:
		print('CHEF')


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


def solve(n, p):
	c1 = 0
	c2 = 0
	for i in p:
		if i == 1:
			c1 += 1
		if i % 2 == 0:
			c2 += 1
	if c1 % 2 == 0 and c2 % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')
t = int(input())
for i in range(t):
	x = int(input())
	y = [int(a) for a in input().split()]
	solve(x, y)


def LII():
	return [int(x) for x in input().split()]

def II():
	return int(input())
for _ in range(int(input())):
	n = II()
	a = LII()
	assert len(a) == n
	nv = 0
	for x in a:
		if x == 1:
			nv ^= 1
		else:
			nv ^= 2 * (1 - x % 2)
	print('CHEF' if nv != 0 else 'CHEFINA')