Chef and Chefina are playing a game involving N piles where the i^{th} pile (1≤ i ≤ N) has A_{i} stones initially.

They take alternate turns with Chef starting the game.

In his/her turn a player can choose any non-empty pile (say i^{th} pile) and remove X stones from it iff:

[Parity] of X is same as parity of i.
1 ≤ X ≤ A_{i}.

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

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

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

The output is case-insensitive. Thus, the strings Chef, CHEF, chef, and cheF are all considered identical.

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

$1 ≤ T ≤ 4000$
$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 ------ 
2
1
2
3
2 1 3

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

----- explanation 1 ------ 
Test case $1$: Chef makes the first move and can only remove $X = 1$ stone from the pile. Thus, the pile has $1$ stone left which Chefina can remove. Chef has no possible move left and thus Chefina wins.  
Note that Chef cannot remove $X = 2$ stones in the first turn as $X$ should have the same parity as $i = 1$.

Test case $2$: It can be shown that if both players play optimally, Chef wins the game.

Source: codechef | Difficulty: VERY_HARD
Tags: Game theory


Solutions:
from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = 0
	ind = 0
	for i in l:
		ind += 1
		if ind % 2 == 0:
			a ^= i // 2
		else:
			a ^= i % 2
	if a != 0:
		print('CHEF')
	else:
		print('CHEFINA')


from functools import reduce
for _ in range(int(input())):
	input()
	grundy = []
	for (i, h) in enumerate([int(x) for x in input().split()], start=1):
		if i % 2 == 0:
			grundy.append(h // 2)
		else:
			grundy.append(h % 2)
	nimn = reduce(lambda x, y: x ^ y, grundy)
	print('CHEF' if nimn > 0 else 'CHEFINA')


def answer():
	xor = 0
	for i in range(n):
		if i + 1 & 1:
			if a[i] & 1:
				xor ^= 1
		else:
			xor ^= a[i] // 2
	if xor:
		return 'CHEF'
	else:
		return 'CHEFINA'
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())