Chef and his best friend Aleksa are into mathematical games these days. Today, they have some ( ≥ 0 ) black cells represented as B, and a white cell represented as W, lying randomly in a straight line.
They have decided to play with these cells. In a move, a player chooses some ( > 0 ) black cells lying on any one side of the white cell and remove them. It should be noted that a player is not allowed to choose black cells from both side of the given white cell. Both the players alternate their moves, and play optimally. The player who is unable to move in his respective turn will lose the game.
Aleksa, being a girl, has a habit of playing first. But Chef is fairly smart himself, and will not play the game if he is going to lose it. Therefore, he wants to know the winner beforehand. Can you tell him who is going to win the game for the given configuration of cells?

-----Input-----
First line of input contains a single integer T denoting the number of test cases. First and the only line of each test case contains a string S consisting of the characters 'B' and 'W', denoting black and white cells, respectively.

-----Output-----
For each test case, output "Chef" if chef wins the game for the given configuration. Else print "Aleksa". (quotes for clarity only).

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ |S| ≤ 10000
- S contains exactly 1 white cell.

-----Scoring-----
-  Subtask 1:  1 ≤ T ≤ 10, 1 ≤ |S| ≤ 10 : ( 30 pts )
-  Subtask 2:  1 ≤ T ≤ 10, 1 ≤ |S| ≤ 100 : ( 30 pts )
-  Subtask 3:  1 ≤ T ≤ 10, 1 ≤ |S| ≤ 10000 : ( 40 pts )

-----Example-----
Input
3
W
BW
BWBB

Output
Chef
Aleksa
Aleksa

----- Explanation-----
-  Test 1 : Aleksa cannot make a move in her first turn as there is no black cell in the given configuration.
-  Test 2 : Aleksa can remove 1 black cell lying on the left of white cell in her turn. But then, Chef cannot make a move in his turn as there will be no black cells left.
-  Test 3 : Figure out yourself.

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
n = int(input())
for i in range(n):
	str1 = input()
	if str1 == 'W':
		print('Chef')
	else:
		cnt = 0
		cnt1 = 0
		l1 = len(str1)
		if l1 % 2 == 0:
			print('Aleksa')
		elif str1[l1 // 2] == 'W':
			print('Chef')
		else:
			print('Aleksa')


for _ in range(int(input())):
	(x, y) = input().split('W')
	if len(x) == len(y):
		print('Chef')
	else:
		print('Aleksa')


for u in range(int(input())):
	(s, r) = input().split('W')
	if len(s) == len(r):
		print('Chef')
	else:
		print('Aleksa')


x = int(input())
for i in range(x):
	n = str(input())
	l = len(n)
	if l % 2 == 0:
		print('Aleksa')
	elif n[l // 2] == 'W':
		print('Chef')
	else:
		print('Aleksa')


t = input()
for i in range(int(t)):
	s = input()
	(l, r, f) = (0, 0, 0)
	for j in s:
		if j == 'W':
			f = 1
			continue
		if f != 1:
			l += 1
		else:
			r += 1
	if l == r:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
for _ in range(t):
	l = list(input())
	ind = l.index('W')
	x = len(l) - 1 - ind
	res = x ^ ind
	if res == 0:
		print('Chef')
	else:
		print('Aleksa')


for _ in range(int(input())):
	s = input()
	n = len(s)
	if n % 2 == 0:
		print('Aleksa')
	elif s[n // 2] == 'W':
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
for i in range(t):
	game = input()
	(x, y) = game.split('W')
	if len(x) == len(y):
		print('Chef')
	else:
		print('Aleksa')


T = int(input())
for _ in range(T):
	L = list(input())
	n = len(L)
	a = L.index('W')
	m1 = L[:a].count('B')
	m2 = L[a + 1:].count('B')
	if m1 == m2:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
for _ in range(t):
	s = input()
	l = len(s)
	k = l // 2
	if len(s) % 2 != 0 and s[k] == 'W':
		print('Chef')
	else:
		print('Aleksa')


for _ in range(int(input())):
	s = input()
	n = len(s)
	if n & 1 and s[n // 2] == 'W':
		print('Chef')
	else:
		print('Aleksa')


for t in range(int(input())):
	S = input().strip()
	n = len(S)
	w = S.index('W')
	if n % 2 == 1 and w == n // 2:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
for i in range(t):
	l = list(input())
	n = len(l)
	p = l.index('W')
	left = p
	right = n - p - 1
	if left ^ right == 0:
		print('Chef')
	else:
		print('Aleksa')


try:
	for i in range(int(input())):
		s = input()
		d = s.find('W')
		l = d - 0
		r = len(s) - 1 - d
		if r == l:
			print('Chef')
		else:
			print('Aleksa')
except:
	pass


for _ in range(int(input())):
	s = input().split('W')
	if len(s[1]) == len(s[0]):
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
while t > 0:
	t = t - 1
	str = input()
	size = len(str)
	pos = str.find('W')
	left = pos
	right = size - pos - 1
	arr = [[0 for i in range(right + 1)] for j in range(left + 1)]
	arr[0][0] = 0
	for i in range(left + 1):
		for j in range(right + 1):
			if i == j:
				arr[i][j] = 0
			else:
				arr[i][j] = 1
	if arr[left][right] == 1:
		print('Aleksa')
	else:
		print('Chef')


t = int(input())
for i in range(0, t):
	s = input()
	if len(s) % 2 == 1 and s.find('W') == len(s) // 2:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	p = s.find('W')
	l = p
	r = n - p - 1
	if l != 0 and r != 0:
		if l != r:
			print('Aleksa')
		else:
			print('Chef')
	elif l == 0 and r != 0:
		print('Aleksa')
	elif l != 0 and r == 0:
		print('Aleksa')
	else:
		print('Chef')


t = int(input())
for tc in range(t):
	s = input()
	a = s.index('W')
	left = []
	right = []
	for i in range(0, a):
		if s[i] == 'B':
			left.append(s[i])
	for i in range(a, len(s)):
		if s[i] == 'B':
			right.append(s[i])
	if len(left) != len(right):
		print('Aleksa')
	else:
		print('Chef')


n = int(input())
for i in range(n):
	st = input().split('W')
	l1 = len(st[0])
	l2 = len(st[1])
	if l1 == l2:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
for i in range(t):
	str = input()
	k = str.index('W')
	if len(str[:k]) == len(str[k + 1:]):
		print('Chef')
	else:
		print('Aleksa')


for _ in range(int(input())):
	list1 = input().split('W')
	a = len(list1[0])
	b = len(list1[1])
	if a == b:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
for _ in range(t):
	n = input()
	left = 0
	right = 0
	x = len(n)
	for i in n:
		if i == 'B':
			left = left + 1
		elif i == 'W':
			break
	right = x - left - 1
	if right == left:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
while t > 0:
	t = t - 1
	str = input()
	size = len(str)
	pos = str.find('W')
	left = pos
	right = size - pos - 1
	if left != 0 and right != 0:
		if left != right:
			print('Aleksa')
		else:
			print('Chef')
	elif left == 0 and right != 0:
		print('Aleksa')
	elif left != 0 and right == 0:
		print('Aleksa')
	else:
		print('Chef')


n = int(input())
for i in range(n):
	s = input()
	k = len(s)
	if k == 1:
		print('Chef')
	elif k == 2:
		print('Aleksa')
	elif k % 2 == 0:
		print('Aleksa')
	elif s[k // 2] == 'W':
		print('Chef')
	else:
		print('Aleksa')


import sys
for i in range(int(input())):
	s = sys.stdin.readline()[:-1]
	bef = 0
	aft = 0
	x = 0
	while s[x] != 'W':
		bef += 1
		x += 1
	x += 1
	while x < len(s):
		aft += 1
		x += 1
	alexa = False
	if bef == aft:
		print('Chef')
	else:
		print('Aleksa')


for _ in range(int(input())):
	l = 0
	r = 0
	f = False
	for w in input():
		if w == 'W':
			f = True
			continue
		if f:
			r = r + 1
		else:
			l = l + 1
	if l == r:
		print('Chef')
	else:
		print('Aleksa')


T = int(input())
for _ in range(T):
	s = str(input())
	(l, r, flag) = (0, 0, 0)
	for ele in s:
		if ele == 'B':
			if flag == 0:
				l += 1
			else:
				r += 1
		else:
			flag = 1
	if l == 0 and r == 0:
		print('Chef')
	elif l == r:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
for i in range(t):
	s = input()
	if s == 'W':
		print('Chef')
	elif s == 'WB' or s == 'BW':
		print('Aleksa')
	else:
		l = list(s)
		le = len(l)
		x = l.index('W')
		l1 = l[0:x]
		l2 = l[x + 1:le]
		le1 = len(l1)
		le2 = len(l2)
		if le1 ^ le2 == 0:
			print('Chef')
		else:
			print('Aleksa')


t = int(input())
for _ in range(t):
	(l, r) = input().split('W')
	if len(l) == len(r):
		print('Chef')
	else:
		print('Aleksa')


for t in range(int(input())):
	s = input()
	w = s.split('W')
	if len(w[0]) == len(w[1]):
		print('Chef')
	else:
		print('Aleksa')


for _ in range(int(input())):
	st = input()
	i = st.index('W')
	length = len(st)
	le = length - i - 1
	ri = length - le - 1
	if le == ri:
		print('Chef')
	else:
		print('Aleksa')


T = int(input())
for t in range(T):
	conf = input()
	if len(conf) % 2 == 0:
		print('Aleksa')
	elif conf.find('W') == (len(conf) - 1) / 2:
		print('Chef')
	else:
		print('Aleksa')


for _ in range(int(input())):
	s = input()
	h = s.index('W')
	left = h
	right = len(s) - 1 - h
	if left == right:
		print('Chef')
	else:
		print('Aleksa')


test_cases = int(input())
for i in range(test_cases):
	string = input()
	a = string.find('W')
	x = a - 0
	y = len(string) - 1 - x
	if y == x:
		print('Chef')
	else:
		print('Aleksa')


n = int(input())
while n:
	string = input()
	c = 0
	for i in range(0, len(string)):
		if string[i] == 'W':
			break
		c += 1
	c1 = len(string) - c - 1
	if c ^ c1:
		print('Aleksa')
	else:
		print('Chef')
	n -= 1


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(10000000.0) + 9
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr: enumerate(itr)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def solve(*args, **kwargs):
	s = args[0]
	blacks = s.split('W')
	return 'Chef' if blacks[0] == blacks[1] else 'Aleksa'

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg2 = inp(str)
		res = solve(*(arg2,))
		if type(res) in {list, tuple, set}:
			print(*res, sep='\n')
		else:
			print(res)
main()


for _ in range(int(input())):
	S = input()
	i = S.index('W')
	l = len(S)
	if l == 1:
		print('Chef')
	elif i == 0 or i == l - 1:
		print('Aleksa')
	else:
		left = i
		right = l - i - 1
		if left == right:
			print('Chef')
		else:
			print('Aleksa')


for i in range(int(input())):
	s = input()
	bef = 0
	aft = 0
	x = 0
	while s[x] != 'W':
		bef += 1
		x += 1
	x += 1
	while x < len(s):
		aft += 1
		x += 1
	alexa = False
	if bef == aft:
		print('Chef')
	else:
		print('Aleksa')


import sys
import math

def main(arr):
	left = 0
	right = 0
	count = 0
	for e in arr:
		if e == 'W':
			left = count
			count = 0
		else:
			count += 1
	right = count
	if left == right:
		return 'Chef'
	else:
		return 'Aleksa'
for _ in range(int(input())):
	a = list(input())
	print(main(a))


for i in range(int(input())):
	s = input()
	l = len(s)
	if l % 2 == 0:
		print('Aleksa')
	elif s[l // 2] == 'W':
		print('Chef')
	else:
		print('Aleksa')


T = 1
T = int(input().strip())
for _ in range(T):
	a = []
	a = input()
	if len(a) % 2 and a.index('W') == len(a) // 2:
		print('Chef')
	else:
		print('Aleksa')


for _ in range(int(input())):
	s = input()
	i = s.find('W')
	c = s.count('B')
	r = s[i:].count('B')
	l = c - r
	if l == r:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
while t > 0:
	s = input()
	n = s.find('W')
	a = len(s[:n])
	b = len(s[n + 1:])
	if a == b:
		print('Chef')
	else:
		print('Aleksa')
	t = t - 1


for _ in range(int(input())):
	s = input()
	i = s.index('W')
	try:
		print('Chef' if len(s[:i]) == len(s[i + 1:]) else 'Aleksa')
	except:
		print('Chef')


for _ in range(int(input())):
	string = input()
	pos = string.index('W')
	l = string[:pos].count('B')
	r = string[pos:].count('B')
	if l == r:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
for i in range(t):
	a = input()
	r = a.partition('W')
	if len(r[0]) == len(r[2]):
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	ind = s.index('W')
	l = s[:ind]
	r = s[ind + 1:]
	if l == r:
		print('Chef')
	else:
		print('Aleksa')


for i in range(int(input())):
	s = input()
	wi = s.index('W')
	l1 = len(s[:wi])
	l2 = 0
	if 'B' in s[wi:]:
		l2 = len(s[wi + 1:])
	if l1 == l2:
		print('Chef')
	else:
		print('Aleksa')


t = int(input())
while t > 0:
	s = input()
	n = len(s)
	if s[(n - 1) // 2] == 'W' and n % 2 != 0:
		print('Chef')
	else:
		print('Aleksa')
	t = t - 1


for i in range(int(input())):
	l = list(input())
	c = 0
	for i in range(len(l)):
		if l[i] == 'W':
			break
		else:
			c += 1
	if c == len(l) - c - 1:
		print('Chef')
	else:
		print('Aleksa')


from itertools import groupby
for _ in range(int(input())):
	(l, r) = map(len, input().split('W'))
	if l == r:
		print('Chef')
	else:
		print('Aleksa')


T = int(input())
for i in range(T):
	string = input()
	w = string.index('W')
	size = len(string)
	if w >= 2 and size - w - 1 >= 2:
		if size - w - 1 == w:
			print('Chef')
		else:
			print('Aleksa')
	elif w <= 1 or size - w - 1 <= 1:
		if w == 1 and size - w - 1 == 1:
			print('Chef')
		elif w == 0 and size - w - 1 == 0:
			print('Chef')
		else:
			print('Aleksa')


t = int(input())
res = []
while t > 0:
	s = input().upper()
	if len(s) == 1:
		res.append('Chef')
	else:
		x = s.index('W')
		if len(s[:x]) == len(s[x + 1:]):
			res.append('Chef')
		else:
			res.append('Aleksa')
	t -= 1
for x in res:
	print(x)


for i in range(int(input())):
	S = input()
	if len(S[:S.index('W')]) == len(S[S.index('W') + 1:]):
		print('Chef')
	else:
		print('Aleksa')


tests = int(input())
for i in range(tests):
	string = input()
	length = len(string)
	if length & 1 and string[length // 2] == 'W':
		print('Chef')
	else:
		print('Aleksa')


for _ in range(int(input())):
	ar = list(input())
	if len(ar) % 2 == 1 and ar.index('W') == int(len(ar) / 2):
		print('Chef')
	else:
		print('Aleksa')


from sys import stdin
ip = stdin.readline
for _ in range(int(ip())):
	s = input()
	if s == 'W':
		print('Chef')
	else:
		d = s
		print('Chef' if s == d[::-1] else 'Aleksa')


t = int(input())
for _ in range(t):
	s = input()
	pos = s.find('W')
	print('Chef' if 2 * pos + 1 == len(s) else 'Aleksa')


t = int(input())
while t:
	t -= 1
	a = input()
	m = a.split('W')
	(n, k) = (len(m[0]), len(m[1]))
	if n == k:
		print('Chef')
	else:
		print('Aleksa')