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: interview

Starter code:

Solutions:
t =int(input()) #no. of test cases
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[i,j] = 1 if with i black cells on left and j on right 1st player can         win, 0 otherwise.
 #Recursion: arr[i][j]= or(arr[x][y])
 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")


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))


# cook your dish here
for u in range(int(input())):
 s,r=input().split('W')
 if(len(s)==len(r)):
  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):
 s=input()
 l=len(s)
 k=l//2
 if (len(s)%2!=0 and s[k]=='W'):
  print('Chef')
 else:
  print('Aleksa')


# cook your dish here
try:
 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')
except:
 pass

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


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

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

# cook your dish here
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")

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 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")
 


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')


t = int(input().strip())
for i in range(t):
 str_data=input()
 x,y=str_data.split("W")
 if (len(x)==len(y)):
  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') 



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")

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

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

for _ in range(int(input())):
 s=input().split('W')
 #print(s)
 if len(s[1])==len(s[0]):
  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")