Chef is a really nice and respectful person, in sharp contrast to his little brother, who is a very nasty and disrespectful person. Chef always sends messages to his friends in all small letters, whereas the little brother sends messages in all capital letters.
You just received a message given by a string s. You don't know whether this message is sent by Chef or his brother. Also, the communication channel through which you received the message is erroneous and hence can flip a letter from uppercase to lowercase or vice versa. However, you know that this channel can make at most K such flips.
Determine whether the message could have been sent only by Chef, only by the little brother, by both or by none.

-----Input-----

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N and K denoting the length of the string s and the maximum number of flips that the erroneous channel can make.
- The second line contains a single string s denoting the message you received.

-----Output-----
For each test case, output a single line containing one string — "chef", "brother", "both" or "none".

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 100
- 0 ≤ K ≤ N
- s consists only of (lowercase and uppercase) English letters

-----Example-----
Input

4
5 1
frauD
5 1
FRAUD
4 4
Life
10 4
sTRAWBerry

Output

chef
brother
both
none

-----Explanation-----
Example case 1: Only one flip is possible. So it is possible that Chef sent "fraud" and the channel flipped the last character to get "frauD". However, it is not possible for the brother to have sent "FRAUD", because then it would need 4 flips. Hence the answer is "chef".
Example case 2: Only one flip is possible. So it is possible that the brother sent "FRAUD" and the channel didn't flip anything. However, it is not possible for Chef to have sent "fraud", because then it would need 5 flips. Hence the answer is "brother".
Example case 3: Four flips are allowed. It is possible that Chef sent "life" and the channel flipped the first character to get "Life". It is also possible that the brother sent "LIFE" and the channel flipped the last three characters to get "Life". Hence the answer is "both".
Example case 4: Four flips are allowed. It is not possible that Chef sent "strawberry", because it would need five flips to get "sTRAWBerry". It is also not possible that the brother sent "STRAWBERRY", because that would also need five flips. Hence the answer is "none".

Difficulty: interview

Starter code:

Solutions:
t=int(input())
def do():
 n,k=map(int,input().split())
 s=input()
 upper=0
 lower=0
 for i in s:
  if i.isupper():
   upper+=1
  else:
   lower+=1
 if lower>k and upper<=k:
  print('chef')
 elif(upper>k and lower<=k):
  print('brother')
 elif(upper<=k and lower<=k):
  print('both')
 else:
  print('none')
 return
for i in range(t):
 do()

# cook your dish here
t=int(input())
def do():
 n,k=list(map(int,input().split()))
 s=input()
 upper=0
 lower=0
 for i in s:
  if i.isupper():
   upper+=1
  else:
   lower+=1
 if lower>k and upper<=k:
  print('chef')
 elif(upper>k and lower<=k):
  print('brother')
 elif(upper<=k and lower<=k):
  print('both')
 else:
  print('none')
 return
for i in range(t):
 do()


# cook your dish here
t = int(input())
for i in range(t):
 n,k =list(map(int,input().split()))
 a = input()
 c=0
 b=0
 for i in a:
  if i.isupper():
   c+=1
  else:
   b+=1
 if c<=k and b>k:
  print("chef")
 elif c>k and b<=k:
  print("brother")
 elif c<=k and b<=k:
  print('both')
 elif c>k and b>k:
  print("none")
 


# cook your dish here
t=int(input())
for i in range(t):
 n,k=[int(i) for i in input().split()]
 s=input()
 u=0
 l=0
 for i in range(len(s)):
  if(s[i].isupper()):
   u+=1 
  else:
   l+=1
 if(u<=k and l<=k):
  print("both")
 elif(l<=k and u>k):
  print("brother")
 elif(u<=k and l>k):
  print("chef")
 else:
  print("none")


# cook your dish here
for i in range(int(input())):
 x,y=list(map(int,input().split()))
 z=input()
 c,s=0,0
 for j in z:
  if j.isupper():c+=1
  else:s+=1
 if c<=y and s<=y:
  print('both')
 elif s<=y:
  print('brother')
 elif c<=y:
  print('chef')
 else:
  print('none') 


# cook your dish here
for _ in range(int(input())):
 n,k=list(map(int,input().split()))
 s=input()
 l=u=0
 for i in s:
  if(i.islower()):
   l+=1
  else:
   u+=1
 if(l<=k and u<=k):
  print("both")
 elif(u>k and l<=k):
  print("brother")
 elif(l>k and u<=k):
  print("chef")
 else:
  print("none")


t=int(input())
for _ in range(t):
 n,k=list(map(int,input().split()))
 s=input()
 l,u=0,0
 for i in range(0,n):
  if(s[i].isupper()):
   u+=1 
  else:
   l+=1 
 if(l<=k and u<=k):
  print("both")
 elif(u>k and l<=k):
  print("brother")
 elif(l>k and u<=k):
  print("chef")
 else:
  print("none")


# cook your dish here
t=int(input())
for i in range(t):
 n,k=[int(i) for i in input().split()]
 s=input()
 u=0
 l=0
 for i in range(len(s)):
  if(s[i].isupper()):
   u+=1 
  else:
   l+=1
 if(u<=k and l<=k):
  print("both")
 elif(l<=k and u>k):
  print("brother")
 elif(u<=k and l>k):
  print("chef")
 else:
  print("none")
   
   
  
  


# cook your dish here
for _ in range(int(input())):
 N,K = map(int,input().split())
 s = input()
 c = 0
 for i in range(N):
  if s[i].islower():
   c+=1
 if K>=c and K>= (N-c):
  print("both")
 elif c>=K and (N-c)<=K:
  print("chef")
 elif c<=K and (N-c)>=K:
  print("brother")
 else:
  print("none")

for _ in range(int(input())):
 N,K=list(map(int,input().split()))
 s=input()
 cap=0
 small=0
 for i in s:
  if ord(i)>=65 and ord(i)<=90:
   cap+=1 
  else:
   small+=1 
 if cap==small:
  if K>=small:
   print('both')
  elif K<small:
   print('none')
 elif small>cap:
  if K>=small:
   print('both')
  elif K<cap:
   print('none')
  else:
   print('chef')
 elif cap>small:
  if K>=cap:
   print('both')
  elif K<small:
   print('none')
  else:
   print('brother')


for _ in range(int(input())):
 N,K=list(map(int,input().split()))
 s=input()
 cap=0
 small=0
 for i in s:
  if ord(i)>=65 and ord(i)<=90:
   cap+=1 
  else:
   small+=1 
 if cap==small:
  if K>=small:
   print('both')
  elif K<small:
   print('none')
 elif small>cap:
  if K>=small:
   print('both')
  elif K<cap:
   print('none')
  else:
   print('chef')
 elif cap>small:
  if K>=cap:
   print('both')
  elif K<small:
   print('none')
  else:
   print('brother')


import sys
import math
import bisect
from math import sqrt
def input():    return sys.stdin.readline().strip()
def iinput():   return int(input())
def rinput():   return map(int, sys.stdin.readline().strip().split()) 
def get_list(): return list(map(int, sys.stdin.readline().strip().split())) 
mod = int(1e9)+7

for _ in range(iinput()):
 n, k = rinput()
 s = input()
 cap = low = 0

 for ch in s:
  if ch.upper() == ch:
   cap += 1
  else:
   low += 1

 # print(cap, low)       

 if cap <= k and low <= k:
  print("both")
 elif cap <= k:
  print("chef")
 elif low <= k:
  print("brother")
 else:
  print("none")

# cook your dish here
for _ in range (int(input())):
 l,flip=map(int,input().split())
 d=input()
 up=d.upper()
 lp=d.lower()
 #print(up,lp)
 ku=0
 kl=0
 for i in range(0,len(d)):
  if(d[i]==up[i]):
   ku+=1
  else:
   kl+=1
 if(ku<=flip and kl<=flip):
  print("both")
 elif(ku<=flip):
  print("chef")
 elif(kl<=flip):
  print("brother")
 else:
  print("none")

T=int(input())
for i in range(T):
 lower,upper=0,0
 N,K=list(map(int,input().split()))
 s=str(input())[:N]
 for j in range(len(s)):
  if(s[j]>='a' and s[j]<='z'):
   lower+=1
  elif(s[j]>='A' and s[j]<='Z'):
   upper+=1
 if lower<=K and upper<=K:
  print("both")
 elif lower<=K and upper>=K:
  print("brother")
 elif lower>=K and upper<=K:
  print("chef")
 elif lower>=K and upper>=K:
  print("none")


T=int(input())
for i in range(T):
 lower,upper=0,0
 N,K=list(map(int,input().split()))
 s=str(input())[:N]
 for j in range(len(s)):
  if(s[j]>='a' and s[j]<='z'):
   lower+=1
  elif(s[j]>='A' and s[j]<='Z'):
   upper+=1
 if lower<=K and upper<=K:
  print("both")
 elif lower<=K and upper>=K:
  print("brother")
 elif lower>=K and upper<=K:
  print("chef")
 elif lower>=K and upper>=K:
  print("none")


# cook your dish here
for t in range(int(input())):
 n,k=list(map(int,input().split()))
 s=input()
 up=0
 lo=0
 for i in s:
  if i.isupper():
   up+=1 
  elif i.islower():
   lo+=1
 if k>=len(s) or (k>=up and k>=lo) :
  print("both")
 else:
  if lo>k and up>k:
   print("none")
  else:
   if k>=lo:
    print("brother")
   elif k>=up:
    print("chef")
    


# cook your dish here
for t in range(int(input())):
 n,k=list(map(int,input().split()))
 s=input()
 up=0
 lo=0
 for i in s:
  if i.isupper():
   up+=1 
  elif i.islower():
   lo+=1
 if k>=len(s) or (k>=up and k>=lo) :
  print("both")
 else:
  if lo>k and up>k:
   print("none")
  else:
   if k>=lo:
    print("brother")
   elif k>=up:
    print("chef")
    


# cook your dish here
for t in range(int(input())):
 n,k=list(map(int,input().split()))
 s=input()
 up=0
 lo=0
 for i in s:
  if i.isupper():
   up+=1 
  elif i.islower():
   lo+=1
 if k>=len(s) or (k>=up and k>=lo) :
  print("both")
 else:
  if lo>k and up>k:
   print("none")
  else:
   if k>=lo:
    print("brother")
   elif k>=up:
    print("chef")
    


def goodandbadPersons(n,k,s):
 if n == k:
  print('both')
 else:
  c = b = 0
  for i in s:
   if i.islower():
    c += 1
   else:
    b += 1
  if k >= c and k >= b:
   print('both')
  elif k >= b:
   print('chef')
  elif k >= c:
   print('brother')
  else:
   print('none')
 return

#Driver code starts here
def __starting_point():
 t = int(input())
 for _ in range(t):
  n,k = map(int,input().split())
  s = input()
  goodandbadPersons(n,k,s)
__starting_point()

# cook your dish here
T= int(input())
for i in range(T):
 N, K= list(map(int, input().split(" ")))
 msg= input()
 lower= 0
 upper= 0
 for s in msg:
  if ord(s) in range(65, 91):
   upper += 1
  elif ord(s) in range(97, 123):
   lower += 1
 if K > N:
  print("both")
 elif lower== upper:
  if K >= lower:
   print("both")
  else:
   print("none")
 elif lower < upper:
  if K < lower:
   print("none")
  elif K >= upper:
   print("both")
  else:
   print("brother")
 elif upper < lower:
  if K< upper:
   print("none")
  elif K>= lower:
   print("both")
  else:
   print("chef")


# cook your dish here
for _ in range(int(input())):
 n,k=map(int,input().split())
 s=input()
 if(n==k):
  print("both")
 else:
  x=0
  y=0
  for i in s:
   if(i.islower()):
    x=x+1
   else:
    y=y+1
  if(k>=x and k>=y):
   print("both")
  elif(k>=y):
   print("chef")
  elif(k>=x):
   print("brother")
  else:
   print("none")

for t in range(int(input())):
 n,k=map(int,input().split())
 s=input()
 if n==k:
  print("both")
 else:
  x=0
  y=0
  for i in s:
   if i.islower():
    x=x+1
   else:
    y=y+1
  if k>=y and k>=x:
   print("both")
  elif k>=y:
   print("chef")
  elif k>=x:
   print("brother")
  else:
   print("none")

for _ in range(int(input())):
 
 n,k = map(int, input().split())
 
 s = input()
 
 uppercase,lowercase = 0,0
 
 for i in s:
  
  if i >= 'a' and i <= 'z':
   
   lowercase += 1
   
  elif i >= 'A' and i <= 'Z':
   
   uppercase += 1
   
 if uppercase <= k and lowercase <= k:
  
  print("both")
  
 elif uppercase <= k and lowercase > k:
  
  print("chef")
  
 elif uppercase > k and lowercase <= k:
  
  print("brother")
  
 else:
  
  print("none")

for _ in range(int(input())):
 n, k = map(int, input().split())
 msg = input()

 small_cnt = cap_cnt = 0

 for char in msg:
  if char.isupper():
   cap_cnt += 1

  elif char.islower():
   small_cnt += 1

 if small_cnt <= k and cap_cnt <= k:
  print("both")
 elif small_cnt <= k and small_cnt < cap_cnt:
  print("brother")
 elif cap_cnt <= k and cap_cnt < small_cnt:
  print("chef")
 elif small_cnt > k and cap_cnt > k:
  print("none")

import collections
from collections import defaultdict
import math

def chef(s,c,k):
 if c<=k:
   return True
 else:
  return False 

def brother(s,c,k):
 if s<=k:
   return True
 else:
  return False


for _ in range(int(input())):
 #n=int(input())
 
 n,k=[int(x) for x in input().split()]
 s= input()
 #n,z=[int(x) for x in input().split()]
 #a=[int(x) for x in input().split()] 
 cap="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 small=cap.lower()
 #chef, brother, both, none
 ss=0
 for x in s:
  if x in small:
   ss+=1
 cc = n-ss 


 ch=chef(ss,cc,k)
 bro=brother(ss,cc,k)
 if ch and bro:
  print("both")
 elif ch and (not bro): 
  print("chef")
 elif (not ch) and (bro):      
  print("brother")
 else:
  print("none")