Chef and Chefina are playing a game. There are two piles numbered 1 and 2.  
Pile 1 contains X stones while Pile 2 contains Y stones.

Chef starts the game.
In his turn, Chef can either remove 1 stone each from both the piles or remove 2 stones from pile 1.
On the other hand, Chefina, in her turn, can either remove 1 stone each from both the piles or remove 2 stones from pile 2.

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 a single line containing two integers X and Y, the initial number of stones in piles 1 and 2 respectively.

------ 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 ≤ X, Y ≤ 10^{9}$

----- Sample Input 1 ------ 
3
1 10
2 2
4 2

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

----- explanation 1 ------ 
Test case $1$: Consider the following sequence of moves:
- Chef removes $1$ stone each from both the piles. Thus, pile $1$ has no stone left while pile $2$ has $9$ stones left.
- Chefina removes $2$ stones from pile $2$. Thus, pile $1$ has no stones left while pile $2$ has $7$ stones left.

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 sequence of moves:
- Chef removes $1$ stone each from both the piles. Thus, pile $1$ has $1$ stone left and pile $2$ has $1$ stone left.
- Chefina removes $1$ stone each from both the piles. Thus, pile $1$ has no stones left and pile $2$ has no stones left.

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

Difficulty: MEDIUM
Tags: Constructive algorithms

Game theory

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x < y:
		if x % 2 == 0:
			print('CHEFINA')
		elif y - x < 2:
			print('CHEF')
		else:
			print('CHEFINA')
	elif y < x:
		if y % 2 == 0:
			if x - y < 2:
				print('CHEFINA')
			else:
				print('CHEF')
		else:
			print('CHEF')
	elif x % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = abs(a - b)
	if a > b:
		if b % 2 == 0:
			if c >= 2:
				print('CHEF')
			else:
				print('CHEFINA')
		else:
			print('CHEF')
	elif b > a:
		if a % 2 == 0:
			print('CHEFINA')
		elif c >= 2:
			print('CHEFINA')
		else:
			print('CHEF')
	elif a % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


t = int(input())
for _ in range(t):
	(a, b) = list(map(int, input().split()))
	if a == b:
		if a % 2:
			print('CHEF')
		else:
			print('CHEFINA')
	elif a > b:
		d = a - b
		if d == 1:
			if a % 2:
				print('CHEFINA')
			else:
				print('CHEF')
		else:
			print('CHEF')
	else:
		d = b - a
		if d == 1:
			if a % 2:
				print('CHEF')
			else:
				print('CHEFINA')
		else:
			print('CHEFINA')


t = int(input())
for i in range(t):
	(x, y) = [int(x) for x in input().split()]
	if x == y:
		if x % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')
	elif x > y:
		d = x - y
		if d == 1:
			if x % 2 == 0:
				print('CHEF')
			else:
				print('CHEFINA')
		else:
			print('CHEF')
	else:
		d = y - x
		if d == 1:
			if x % 2 == 0:
				print('CHEFINA')
			else:
				print('CHEF')
		else:
			print('CHEFINA')


for i in range(int(input())):
	a = list(map(int, input().split()))
	(x, y) = (a[0], a[1])
	if x == y and x % 2 == 0:
		print('CHEFINA')
	elif x == y and x % 2 != 0:
		print('CHEF')
	elif x < y and x % 2 == 0:
		print('CHEFINA')
	elif x < y and y - x < 2 and (x % 2 != 0):
		print('CHEF')
	elif x < y and y - x >= 2 and (x % 2 != 0):
		print('CHEFINA')
	elif y < x and y % 2 != 0:
		print('CHEF')
	elif y < x and x - y >= 2 and (y % 2 == 0):
		print('CHEF')
	elif y < x and x - y < 2 and (y % 2 == 0):
		print('CHEFINA')


t = int(input())
for _ in range(t):
	(a, b) = [int(x) for x in input().split()]
	rem = abs(a - b)
	if rem == 1:
		if a > b:
			if b % 2 == 0:
				print('CHEFINA')
			else:
				print('CHEF')
		elif a % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')
	elif a > b:
		print('CHEF')
	elif a < b:
		print('CHEFINA')
	elif a % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		if a % 2:
			print('CHEF')
		else:
			print('CHEFINA')
	if a < b:
		d = b - a
		if d != 1:
			print('CHEFINA')
		elif d == 1 and a % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')
	if a > b:
		d = a - b
		if d != 1:
			print('CHEF')
		elif d == 1 and a % 2 == 0:
			print('CHEF')
		else:
			print('CHEFINA')


for tc in range(int(input())):
	(x, y) = map(int, input().split())
	if abs(x - y) < 2:
		if min(x, y) % 2 == 1:
			print('CHEF')
		else:
			print('CHEFINA')
	elif x > y:
		print('CHEF')
	else:
		print('CHEFINA')


try:
	t = int(input())
	while t:
		(x, y) = map(int, input().split())
		if x == y:
			if x % 2:
				print('CHEF')
			else:
				print('CHEFINA')
		elif x > y:
			d = x - y
			if d == 1:
				if x % 2:
					print('CHEFINA')
				else:
					print('CHEF')
			else:
				print('CHEF')
		else:
			d = y - x
			if d == 1:
				if y % 2:
					print('CHEFINA')
				else:
					print('CHEF')
			else:
				print('CHEFINA')
except EOFError as e:
	pass


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	diff = abs(x - y)
	if diff > 1:
		if x == max(x, y):
			print('CHEF')
		else:
			print('CHEFINA')
	elif diff == 0:
		if x == 1:
			print('CHEF')
		elif x % 2:
			print('CHEF')
		else:
			print('CHEFINA')
	elif min(x, y) % 2:
		print('CHEF')
	else:
		print('CHEFINA')


def find_winner(X, Y):
	winner = 'CHEFINA'
	diff = X - Y
	if diff >= 2 or (abs(diff) <= 1 and min(X, Y) % 2 == 1):
		winner = 'CHEF'
	return winner
n = int(input())
for i in range(n):
	(X, Y) = map(int, input().split())
	print(find_winner(X, Y))


times = int(input())
for _ in range(times):
	(pile1, pile2) = list(map(int, input().split()))
	m = min(pile1, pile2)
	pile1 -= m
	pile2 -= m
	turn = 1 + m
	if turn % 2 == 1:
		print('CHEFINA' if pile1 <= 1 else 'CHEF')
	elif turn % 2 == 0:
		print('CHEF' if pile2 <= 1 else 'CHEFINA')


t = int(input())
while t > 0:
	(x, y) = map(int, input().split())
	if x == y:
		if x % 2:
			print('CHEF')
		else:
			print('CHEFINA')
	elif x > y:
		if x - y >= 2:
			print('CHEF')
		elif x % 2:
			print('CHEFINA')
		else:
			print('CHEF')
	elif y - x >= 2:
		print('CHEFINA')
	elif x % 2:
		print('CHEF')
	else:
		print('CHEFINA')
	t -= 1


n = int(input())
while n > 0:
	(x, y) = map(int, input().split())
	if x >= y + 2:
		print('CHEF')
	elif x == y + 1 and x % 2 == 0:
		print('CHEF')
	elif y == x + 1 and y % 2 == 0:
		print('CHEF')
	elif x == y and x % 2 == 1:
		print('CHEF')
	else:
		print('CHEFINA')
	n -= 1


t = int(input())
for cases in range(t):
	(x, y) = map(int, input().split(' '))
	if x >= y + 2:
		print('CHEF')
	elif x == y + 1 and x % 2 == 0:
		print('CHEF')
	elif y == x + 1 and y % 2 == 0:
		print('CHEF')
	elif x == y and x % 2 == 1:
		print('CHEF')
	else:
		print('CHEFINA')


for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		if a % 2:
			print('CHEF')
		else:
			print('CHEFINA')
	elif a > b:
		d = a - b
		if d == 1:
			if a % 2:
				print('CHEFINA')
			else:
				print('CHEF')
		else:
			print('CHEF')
	else:
		d = b - a
		if d == 1:
			if a % 2:
				print('CHEF')
			else:
				print('CHEFINA')
		else:
			print('CHEFINA')


for i in range(int(input())):
	(X, Y) = map(int, input().split())
	if X == Y:
		if X % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')
	elif X > Y:
		Z = X - Y
		if Z == 1:
			if X % 2 == 0:
				print('CHEF')
			else:
				print('CHEFINA')
		else:
			print('CHEF')
	else:
		Z = Y - X
		if Z == 1:
			if X % 2 == 0:
				print('CHEFINA')
			else:
				print('CHEF')
		else:
			print('CHEFINA')


for i in range(int(input())):
	(x, y) = list(map(int, input().split()))
	if abs(x - y) == 1:
		if min(x, y) % 2 != 0:
			print('CHEF')
		else:
			print('CHEFINA')
		continue
	if x > y:
		print('CHEF')
	elif x < y:
		print('CHEFINA')
	elif x % 2 != 0:
		print('CHEF')
	else:
		print('CHEFINA')


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def dfs(n, k):
	diff = abs(n - k)
	if diff >= 2:
		if n > k:
			print('CHEF')
		else:
			print('CHEFINA')
	elif diff == 0:
		if n % 2:
			print('CHEF')
		else:
			print('CHEFINA')
	elif diff == 1:
		mini = min(n, k)
		if mini % 2:
			print('CHEF')
		else:
			print('CHEFINA')
tried = int(input())
for _ in range(tried):
	(n, k) = mul()
	dfs(n, k)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	mi = min(a, b)
	if mi % 2 == 0 and (abs(a - b) == 1 or a == b):
		print('CHEFINA')
	elif mi % 2 != 0 and (abs(a - b) == 1 or a == b):
		print('CHEF')
	elif a > b:
		print('CHEF')
	else:
		print('CHEFINA')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	mn = min(a, b)
	a -= mn - 1
	b -= mn - 1
	mn -= 1
	if mn % 2 == 1:
		if a == 1:
			print('CHEFINA')
		elif a > 2:
			print('CHEF')
		else:
			print('CHEFINA')
	elif b == 1:
		print('CHEF')
	elif b > 2:
		print('CHEFINA')
	else:
		print('CHEF')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if n > m:
		if n % 2 == 1 and m == n - 1:
			print('CHEFINA')
		else:
			print('CHEF')
	elif n == m:
		if n % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')
	elif n % 2 == 1 and m == n + 1:
		print('CHEF')
	else:
		print('CHEFINA')


for tc in range(int(input())):
	(X, Y) = map(int, input().split(' '))
	if X > Y:
		d = X - Y
		if Y % 2 == 0:
			if d > 1:
				print('CHEF')
			else:
				print('CHEFINA')
		elif d > 0:
			print('CHEF')
		else:
			print('CHEFINA')
	elif X == Y:
		if Y % 2 == 0:
			print('CHEFINA')
		else:
			print('CHEF')
	else:
		d = Y - X
		if X % 2 == 0:
			print('CHEFINA')
		elif d > 1:
			print('CHEFINA')
		else:
			print('CHEF')


fuck = int(input())
while fuck > 0:
	a = list(map(int, input().split()))
	if a[1] > a[0] + 1:
		print('CHEFINA')
	elif a[0] % 2 == 0 and a[1] == a[0]:
		print('CHEFINA')
	elif a[0] + 1 == a[1] and a[0] % 2 == 0:
		print('CHEFINA')
	elif a[0] - 1 == a[1] and a[1] % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')
	fuck -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	k = min(a, b)
	a -= k
	b -= k
	if k % 2 == 0:
		if a >= 2:
			print('CHEF')
		else:
			print('CHEFINA')
	elif b >= 2:
		print('CHEFINA')
	else:
		print('CHEF')


k = int(input())
for q in range(k):
	(a, b) = map(int, input().split())
	if a == b + 1 and a % 2 != 0:
		print('CHEFINA')
	elif a == b + 1 and b > 1:
		print('CHEF')
	elif b == a + 1 and a % 2 == 0:
		print('CHEFINA')
	elif b == a + 1:
		print('CHEF')
	elif b > a:
		print('CHEFINA')
	elif a > b:
		print('CHEF')
	elif a % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')


import sys
next((f := sys.stdin))
for s in f:
	(x, y) = map(int, s.split())
	d = y - x
	print('CHEF' + 'INA' * (d > 1 or (d > -2 and x + y & 2 == 0)))


test_cases = int(input())
while test_cases:
	str = input()
	(a, b) = str.split(' ')
	a = int(a)
	b = int(b)
	if a - b > 1:
		print('CHEF')
	elif b - a > 1:
		print('CHEFINA')
	elif a > b:
		if a % 2 == 0:
			print('CHEF')
		else:
			print('CHEFINA')
	elif a % 2 == 0:
		print('CHEFINA')
	else:
		print('CHEF')
	test_cases -= 1


T = int(input())
for i in range(T):
	(X, Y) = map(int, input().split())
	if X == Y:
		if X % 2 != 0:
			print('CHEF')
			continue
		else:
			print('CHEFINA')
			continue
	diff = abs(X - Y)
	if diff >= 2 and X > Y:
		print('CHEF')
		continue
	elif diff >= 2 and X < Y:
		print('CHEFINA')
		continue
	if X % 2 != 0 and X > Y:
		print('CHEFINA')
		continue
	elif X % 2 == 0 and X > Y:
		print('CHEF')
		continue
	elif Y % 2 == 0 and Y > X:
		print('CHEF')
		continue
	elif Y % 2 != 0 and Y > X:
		print('CHEFINA')
		continue


for cases in range(int(input())):
	(X, Y) = map(int, input().split())
	if X == Y:
		print('CHEFINA') if X % 2 == 0 else print('CHEF')
	elif Y > X:
		if Y - X >= 2:
			print('CHEFINA')
		elif X % 2 != 0:
			print('CHEF')
		else:
			print('CHEFINA')
	elif X - Y >= 2:
		print('CHEF')
	elif X % 2:
		print('CHEFINA')
	else:
		print('CHEF')


case = int(input())
for _ in range(case):
	(x, y) = map(int, input().split(' '))
	if x == y:
		if x & 1 == 1:
			print('CHEF')
		else:
			print('CHEFINA')
	else:
		min_val = min(x, y)
		diff = min_val - 1
		curr = 'CHEF'
		if diff & 1 == 1:
			curr = 'CHEFINA'
		else:
			curr = 'CHEF'
		x -= diff
		y -= diff
		if max(x, y) == 2:
			print(curr)
		elif x > y:
			print('CHEF')
		else:
			print('CHEFINA')


mod_ = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	if x == y:
		if x % 2:
			print('CHEF')
		else:
			print('CHEFINA')
	elif abs(x - y) == 1:
		if x > y:
			if x % 2:
				print('CHEFINA')
			else:
				print('CHEF')
		if x < y:
			if x % 2:
				print('CHEF')
			else:
				print('CHEFINA')
	elif x > y:
		print('CHEF')
	else:
		print('CHEFINA')