It's New Year's Day, and Balsa and Koca are stuck inside watching the rain. They decide to invent a game, the rules for which are described below.

Given array $\boldsymbol{a}$ containing $n$ integers, they take turns making a single move. Balsa always moves first, and both players are moving optimally (playing to win and making no mistakes).

During each move, the current player chooses one element from $\boldsymbol{a}$, adds it to their own score, and deletes the element from $\boldsymbol{a}$; because the size of $\boldsymbol{a}$ decreases by $\mbox{1}$ after each move, $\boldsymbol{a}$'s size will be $\mbox{0}$ after $n$ moves and the game ends (as all elements were deleted from $\boldsymbol{a}$). We refer to Balsa's score as $S_{b}$ and Koca's score as $S_{k}$. Koca wins the game if |$S_{b}$-$S_{k}$| is divisible by $3$; otherwise Balsa wins. 

Given $\boldsymbol{a}$, determine the winner.

Note: $S_b+S_k=a_0+a_1+...+a_{n-2}+a_{n-1}$.

Input Format

The first line contains an integer, $\mathbf{T}$, denoting the number of test cases. 

Each test case is comprised of two lines; the first line has an integer $n$, and the second line has $n$ space-separated integers $a_0,a_1,\ldots,a_{n-2},a_{n-1}$ describing array $\boldsymbol{a}$.

Constraints

$1\leq T\leq100$

$1\leq a_i\leq2000$

$1\leq n\leq2000$

Subtasks

For $50\%$ score: $1\leq n\leq200$

For $\textbf{100\%}$ score: $1\leq n\leq2000$

Output Format

For each test case, print the winner's name on a single line; if Balsa wins print Balsa, otherwise print Koca.

Sample Input
2 
3
7 6 18
1
3

Sample Output
Balsa
Koca

Explanation

Test Case 1

Array $a=\{7,6,18\}$. The possible play scenarios are:

$S_b=13$, $S_k=18$, $|S_b-S_k|=5$, and $5\%3\neq0$.

$S_b=24$, $S_k=7$, $|S_b-S_k|=17$, and $17\%3\neq0$.

$S_b=25$, $S_k=6$, $|S_{b}$-$S_k|=19$, and $19\%3\neq0$.

In this case, it doesn't matter what Balsa chooses because the difference between their scores isn't divisible by $3$. Thus, Balsa wins.

Test Case 2

Array $a=\{3\}$. Balsa must choose that element, the first move ends the game. 

$S_b=3$, $S_k=0$, $|S_b-S_k|=3$, and $3\%3=0$. Thus, Koca wins.

Difficulty: MEDIUM
Tags: Game theory

Starter code:

Solutions:
import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	x = [0, 0, 0]
	for i in a:
		x[i % 3] += 1
	x[0] = x[0] & 1
	x[1] = x[1] & 1
	x[2] = x[2] & 1
	if x[0] == x[1] == x[2] == 0:
		print('Koca')
	elif x[0] == x[1] == 0:
		print('Balsa')
	elif x[0] == x[2] == 0:
		print('Balsa')
	elif x[1] == x[2] == 0:
		print('Koca')
	elif x[0] == x[1] == 1:
		print('Balsa')
	elif x[0] == x[2] == 1:
		print('Balsa')
	elif x[1] == x[2] == 1:
		print('Balsa')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	x0 = len([x for x in a if x % 3 == 0]) % 2
	x1 = len([x for x in a if x % 3 == 1]) % 2
	x2 = len([x for x in a if x % 3 == 2]) % 2
	if x1 == 0 and x2 == 0:
		print('Koca')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	num1 = 0
	num2 = 0
	for i in a:
		if i % 3 == 1:
			num1 += 1
		elif i % 3 == 2:
			num2 += 1
	print('Balsa' if num1 % 2 == 1 or num2 % 2 == 1 else 'Koca')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) % 3 for a_temp in input().strip().split(' ')]
	a0 = a.count(0) % 2
	a1 = a.count(1) % 2
	a2 = a.count(2) % 2
	code = a0 + 2 * a1 + 4 * a2
	if code < 2:
		print('Koca')
	else:
		print('Balsa')


from collections import Counter
cnt = Counter()
n = int(input())
for _ in range(n):
	k = int(input())
	arr = list(map(int, input().strip().split(' ')))
	for i in range(k):
		arr[i] = arr[i] % 3
	new = dict(Counter(arr))
	if new.get(1, 0) % 2 == 0 and new.get(2, 0) % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import sys
from itertools import permutations

def eval_scenarios(a):
	s1 = 0
	s2 = 0
	s3 = 0
	for ai in a:
		if ai % 3 == 0:
			s1 += 1
		elif ai % 3 == 1:
			s2 += 1
		elif ai % 3 == 2:
			s3 += 1
	if s2 % 2 == 0 and s3 % 2 == 0:
		return 'Koca'
	return 'Balsa'
T = int(input().strip())
for _ in range(T):
	input()
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	print(eval_scenarios(a))


for t in range(int(input())):
	n = int(input())
	res_1 = 0
	res_2 = 0
	for a_i in list(map(int, input().split())):
		if a_i % 3 == 1:
			res_1 += 1
		elif a_i % 3 == 2:
			res_2 += 1
	print(['Balsa', 'Koca'][res_1 % 2 == 0 and res_2 % 2 == 0])


import sys
from collections import Counter
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) % 3 for a_temp in input().strip().split(' ')]
	c = Counter(a)
	if c[1] % 2 == 0 and c[2] % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	a = [ele % 3 for ele in a]
	positions = [0] * 3
	for i in range(n):
		positions[a[i]] += 1
	if (positions[1] % 2 == 0) & (positions[2] % 2 == 0):
		print('Koca')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	txor_sums = [0, 0, 0]
	for el in a:
		mod = el % 3
		txor_sums[mod] += 1
	if txor_sums[1] % 2 == 0 and txor_sums[2] % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	if n % 2 == 1:
		a.append(0)
	remainders = [x % 3 for x in a]
	zeroes = remainders.count(0)
	ones = remainders.count(1)
	twos = remainders.count(2)
	winner = 'Koca'
	if any((x % 2 == 1 for x in (zeroes, ones, twos))):
		winner = 'Balsa'
	print(winner)


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	remainders = [x % 3 for x in a]
	ones = remainders.count(1)
	twos = remainders.count(2)
	winner = 'Koca'
	if ones % 2 == 1 or twos % 2 == 1:
		winner = 'Balsa'
	print(winner)


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	remainders = [x % 3 for x in a]
	ones = remainders.count(1)
	twos = remainders.count(2)
	winner = 'Koca'
	if ones % 2 == 1 or twos % 2 == 1:
		winner = 'Balsa'
	print(winner)


times = int(input().strip())
for time in range(times):
	elements = int(input().strip())
	list_values = [0, 0, 0]
	for number in [int(number) for number in input().strip().split(' ')]:
		list_values[number % 3] += 1
	if list_values[1] % 2 == 0 and list_values[2] % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	chance = True
	x = 0
	for i in range(n):
		x = x ^ a[i] % 3
	if x != 0:
		print('Balsa')
	else:
		print('Koca')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	f = 0
	g = 0
	h = 0
	for number in a:
		if number % 3 == 0:
			f = f + 1
		elif number % 3 == 1:
			g = g + 1
		else:
			h = h + 1
	if g % 2 == 0 and h % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	txor_sums = [0, 0, 0]
	for el in a:
		mod = el % 3
		txor_sums[mod] += 1
	if txor_sums[1] % 2 == 0 and txor_sums[2] % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	a = list(map(lambda x: x % 3, a))
	if a.count(1) % 2 == 0 and a.count(2) % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	elements = {0: 0, 1: 0, 2: 0}
	for v in a:
		elements[v % 3] += 1
	if elements[1] % 2 == 0 and elements[2] % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


def main():
	T = int(input())
	V = set([(0, 1, 0), (0, 0, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 1, 1)])
	for t in range(T):
		N = int(input())
		R = [int(i) for i in input().split()]
		Q = [0, 0, 0]
		for r in R:
			Q[r % 3] += 1
		S = (Q[0] % 2, Q[1] % 2, Q[2] % 2)
		if S in V:
			print('Balsa')
		else:
			print('Koca')
	return
main()


import sys
import math

def mod3game(n, arr, num3):
	if n == 0:
		return True
	if n == 1:
		if arr[0] % 3 == 0:
			return True
		else:
			return False
	if n == 2:
		if abs(arr[0] - arr[1]) % 3 == 0:
			return True
		else:
			return False

def num3s(n, arr):
	num1 = 0
	num2 = 0
	N = n
	count = 0
	for i in range(n):
		if arr[i - count] % 3 == 0:
			del arr[i - count]
			count += 1
		else:
			arr[i - count] %= 3
	for i in range(len(arr)):
		if arr[i] % 3 == 1:
			num1 += 1
		else:
			num2 += 1
	if num1 % 2 == 0 and num2 % 2 == 0:
		return True
	else:
		return False
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	if num3s(n, a):
		print('Koca')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	winner = 'Balsa'
	(o, t) = (0, 0)
	for _ in a:
		if _ % 3 == 1:
			o = o + 1
		elif _ % 3 == 2:
			t = t + 1
	if o % 2 == 0 and t % 2 == 0:
		winner = 'Koca'
	print(winner)


for _ in range(int(input())):
	n = int(input())
	(c1, c2) = (0, 0)
	for xs in input().split(' '):
		x = int(xs) % 3
		if x:
			if x & 1:
				c1 += 1
			else:
				c2 += 1
	print('Balsa' if (c1 | c2) & 1 else 'Koca')


import sys
T = int(input().strip())
for i in range(T):
	n = int(input().strip())
	a_list = [int(j) for j in input().strip().split(' ')]
	a_mod_3_list = [i % 3 for i in a_list]
	a_ZERO_mod_3_list = [i for i in a_mod_3_list if i == 0]
	a_ONE_mod_3_list = [i for i in a_mod_3_list if i == 1]
	a_TWO_mod_3_list = [i for i in a_mod_3_list if i == 2]
	len_a_ZERO_mod_3_list = len(a_ZERO_mod_3_list) % 2
	len_a_ONE_mod_3_list = len(a_ONE_mod_3_list) % 2
	len_a_TWO_mod_3_list = len(a_TWO_mod_3_list) % 2
	if len_a_ONE_mod_3_list == 0 and len_a_TWO_mod_3_list == 0:
		result = 'Koca'
	else:
		result = 'Balsa'
	print(result)


T = int(input())
for t in range(T):
	n = int(input())
	a = [int(x) for x in input().split()]
	c = 0
	for x in a:
		c ^= 1 << x % 3
	print('Balsa' if c & 6 else 'Koca')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	new_arr = sorted([x % 3 for x in arr])
	n_0 = new_arr.count(0)
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	if n_1 % 2 == 0 and n_2 % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


from collections import Counter
for _ in range(int(input())):
	(_, a) = (input(), map(int, input().split()))
	c = Counter((x % 3 for x in a))
	print('Balsa' if c[1] & 1 or c[2] & 1 else 'Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys

def choose(arr, current_player, scores):
	idx = random.randrange(0, len(arr))
	if current_player == 0:
		for (idx, i) in enumerate(arr):
			if (scores[0] + i - scores[1]) % 3 != 0:
				e = idx
				break
	else:
		for (idx, i) in enumerate(arr):
			if (scores[0] - (scores[1] + i)) % 3 == 0:
				e = idx
				break
	return idx

def game(arr):
	current_player = 0
	scores = [0, 0]
	while len(arr) > 0:
		idx = choose(arr, current_player, scores)
		e = arr.pop(idx)
		scores[current_player] += e
		current_player ^= 1
	if (scores[0] - scores[1]) % 3 == 0:
		print('Koca')
	else:
		print('Balsa')
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	d = dict()
	for num in a:
		if num % 3 in d:
			d[num % 3] += 1
		else:
			d[num % 3] = 1
	check = True
	for num in d:
		if num != 0 and d[num] % 2 != 0:
			print('Balsa')
			check = False
			break
	if check:
		print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	c0 = 0
	c1 = 0
	c2 = 0
	for a in arr:
		if a % 3 == 0:
			c0 += 1
		if a % 3 == 1:
			c1 += 1
		if a % 3 == 2:
			c2 += 1
	if c1 % 2 == 0 and c2 % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
import functools

def result(arr):
	arr = [x % 3 for x in arr]
	if arr.count(1) % 2 + arr.count(2) % 2:
		return 'Balsa'
	return 'Koca'
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	print(result(a))


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	r = [0, 0, 0]
	for x in a:
		r[x % 3] += 1
	ans = r[1] % 2 | r[2] % 2
	print('Balsa' if ans else 'Koca')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for x in l:
		l1.append(x % 3)
	cnt_1 = l1.count(1)
	cnt_2 = l1.count(2)
	if cnt_1 % 2 != 0 or cnt_2 % 2 != 0:
		print('Balsa')
	else:
		print('Koca')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for x in l:
		l1.append(x % 3)
	cnt_1 = l1.count(1)
	cnt_2 = l1.count(2)
	if cnt_1 % 2 != 0 or cnt_2 % 2 != 0:
		print('Balsa')
	else:
		print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	(x1, x2, x3) = (0, 0, 0)
	for i in a:
		if i % 3 == 0:
			x1 += 1
		elif i % 3 == 1:
			x2 += 1
		elif i % 3 == 2:
			x3 += 1
	if x2 % 2 == 0 and x3 % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mods = [i % 3 for i in arr]
	d = dict()
	(d[1], d[2]) = (0, 0)
	for i in mods:
		if i in d:
			d[i] += 1
	if d[1] & 1 | d[2] & 1:
		print('Balsa')
	else:
		print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	p = 0
	q = 0
	r = 0
	for items in a:
		if items % 3 == 0:
			p = p + 1
		elif items % 3 == 1:
			q = q + 1
		elif items % 3 == 2:
			r = r + 1
		else:
			pass
	if p % 2 == 0 and q % 2 == 0 and (r % 2 == 0) or (p % 2 != 0 and q % 2 == 0 and (r % 2 == 0)):
		print('Koca')
	else:
		print('Balsa')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	arr = [0] * 3
	for i in a:
		arr[i % 3] += 1
	if arr[1] % 2 == 0 and arr[2] % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


def dis_winner(arr):
	arr = [x % 3 for x in arr]
	arr = filter(lambda k: k != 0, arr)
	freq = {1: 0, 2: 0}
	for i in arr:
		freq[i] += 1
	if freq[1] % 2 == 0 and freq[2] % 2 == 0:
		print('Koca')
	else:
		print('Balsa')

def main():
	num_tests = int(input())
	for test in range(num_tests):
		size = int(input())
		arr = [int(x) for x in input().split(' ')]
		dis_winner(arr)
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [e % 3 for e in a]
	(one, two) = (b.count(1), b.count(2))
	if one & 1 | two & 1:
		print('Balsa')
	else:
		print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	mod_a = [x % 3 for x in a]
	num_1 = mod_a.count(1)
	num_2 = mod_a.count(2)
	if num_1 & 1 or num_2 & 1:
		print('Balsa')
	else:
		print('Koca')


import math
import os
import random
import re
import sys
from itertools import combinations
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
from itertools import combinations
from math import ceil
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	mod_0 = 0
	mod_1 = 0
	mod_2 = 0
	for element in a:
		if element % 3 == 0:
			mod_0 += 1
		elif element % 3 == 1:
			mod_1 += 1
		else:
			mod_2 += 1
	if (n % 2 == 0) & (mod_0 % 2 == 0) & (mod_1 % 2 == 0) & (mod_2 % 2 == 0):
		print('Koca')
	elif (n % 2 == 1) & (mod_0 % 2 == 1) & (mod_1 % 2 == 0) & (mod_2 % 2 == 0):
		print('Koca')
	else:
		print('Balsa')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	temp = []
	for i in range(len(a)):
		if a[i] % 3 not in temp:
			temp.append(a[i] % 3)
		else:
			j = temp.index(a[i] % 3)
			temp.pop(j)
	if sum(temp) == 0:
		print('Koca')
	else:
		print('Balsa')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	z = {0: 0, 1: 0, 2: 0}
	for i in a:
		z[i % 3] += 1
	if z[1] & 1 | z[2] & 1:
		print('Balsa')
	else:
		print('Koca')


import math, os, random, re, sys, itertools
from collections import Counter

def kocaDiv3ElseBalsaRecursive(c):
	assert len(c) == 3
	memo = {}

	def f2(c0, c1, c2, y):
		ret = memo.get((c0, c1, c2, y))
		if ret is None:
			ret = memo[c0, c1, c2, y] = f(c0, c1, c2, y)
		return ret

	def f(c0, c1, c2, y):
		if True:
			if c1 == 0 and c2 == 0:
				return y != 0
			if c0 == 0 and c1 == 0:
				return (2 * (c2 // 2) + 2 * (c2 % 2)) % 3 != y
			if c0 == 0 and c2 == 0:
				return (1 * (c1 // 2) + 1 * (c1 % 2)) % 3 != y
		k = c0 + c1 + c2
		if c0 > 0:
			while True:
				if k == 1:
					if y != 0:
						return True
					break
				if c0 - 1 > 0:
					if not f2(c0 - 2, c1, c2, y):
						break
				if c1 > 0:
					if not f2(c0 - 1, c1 - 1, c2, y):
						break
				if c2 > 0:
					if not f2(c0 - 1, c1, c2 - 1, y):
						break
				return True
		if c1 > 0:
			y = (y + 2) % 3
			while True:
				if k == 1:
					if y != 1:
						return True
					break
				if c0 > 0:
					if not f2(c0 - 1, c1 - 1, c2, y):
						break
				if c1 - 1 > 0:
					if not f2(c0, c1 - 2, c2, y):
						break
				if c2 > 0:
					if not f2(c0, c1 - 1, c2 - 1, y):
						break
				return True
		if c2 > 0:
			y = (y + 1) % 3
			while True:
				if k == 1:
					if y != 2:
						return True
					break
				if c0 > 0:
					if not f2(c0 - 1, c1, c2 - 1, y):
						break
				if c1 > 0:
					if not f2(c0, c1 - 1, c2 - 1, y):
						break
				if c2 - 1 > 0:
					if not f2(c0, c1, c2 - 2, y):
						break
				return True
		if k == 0:
			return y != 0
		else:
			return False
	return f2(c[0], c[1], c[2], 0)

def computeTable():
	d = {}
	for c in itertools.product([0, 1], repeat=3):
		c = tuple(c)
		d[c] = kocaDiv3ElseBalsaRecursive(c)
	return d
table = [None]

def kocaDiv3ElseBalsa(a):
	if table[0] is None:
		table[0] = computeTable()
	c = Counter([x % 3 for x in a])
	c = (c[0] % 2, c[1] % 2, c[2] % 2)
	res = table[0][c]
	return 'Balsa' if table[0][c] else 'Koca'

def main():
	T = int(input())
	for T_itr in range(T):
		n = int(input())
		a = list(map(int, input().rstrip().split()))
		print(kocaDiv3ElseBalsa(a))
main()


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	if n_1 & 1 | n_2 & 1 == 1:
		print('Balsa')
	else:
		print('Koca')


import sys

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		A = list(map(int, sys.stdin.readline().split()))
		R = [0] * 3
		for a in A:
			R[a % 3] += 1
		sys.stdout.write('Balsa\n' if not R[1] & 1 == R[2] & 1 == 0 else 'Koca\n')
main()


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	winner = ''
	if n == 1:
		winner = 'Koca' if a[0] % 3 == 0 else 'Balsa'
	elif n == 2:
		winner = 'Koca' if abs(a[0] - a[1]) % 3 == 0 else 'Balsa'
	else:
		result = 0
		for e in a:
			result ^= e % 3
		winner = 'Koca' if result == 0 else 'Balsa'
	print(winner)


import math
import os
import random
import re
import sys

def findWinner(a):
	mod1 = []
	mod2 = []
	for i in a:
		if i % 3 == 1:
			mod1.append(i)
		elif i % 3 == 2:
			mod2.append(i)
	if len(mod1) % 2 == 0 and len(mod2) % 2 == 0:
		return 'Koca'
	else:
		return 'Balsa'
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	winner = findWinner(a)
	print(winner)


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	arr = [x % 3 for x in a]
	n_1 = arr.count(1)
	n_2 = arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	if n_1 & 1 | n_2 & 1:
		print('Balsa')
	else:
		print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	num1 = 0
	num2 = 0
	for i in a:
		if i % 3 == 1:
			num1 += 1
		elif i % 3 == 2:
			num2 += 1
	print('Balsa' if num1 % 2 == 1 or num2 % 2 == 1 else 'Koca')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	res = [i % 3 for i in a]
	ones = res.count(1)
	twos = res.count(2)
	if ones % 2 == 0 and twos % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	x0 = len([x for x in a if x % 3 == 0]) % 2
	x1 = len([x for x in a if x % 3 == 1]) % 2
	x2 = len([x for x in a if x % 3 == 2]) % 2
	if x1 == 0 and x2 == 0:
		print('Koca')
	else:
		print('Balsa')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in a]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	if n_1 & 1 | n_2 & 1:
		print('Balsa')
	else:
		print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	a_mod = [i % 3 for i in a]
	two = a_mod.count(2)
	one = a_mod.count(1)
	if one % 2 == 0 and two % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	test = list(sorted(map(lambda x: x % 3, a)))
	val = abs(sum(test[0::2]) - sum(test[1::2]))
	print('Balsa' if val != 0 else 'Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	aa = list(map(lambda x: x % 3, a))
	n2 = aa.count(2)
	n1 = aa.count(1)
	if n2 % 2 == 0 and n1 % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	zeros = sum((a % 3 == 0 for a in arr))
	ones = sum((a % 3 == 1 for a in arr))
	twos = sum((a % 3 == 2 for a in arr))
	if ones % 2 == 0 and twos % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import math
import os
import random
import re
import sys
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	gr = [x % 3 for x in a]
	s = gr.count(1)
	k = gr.count(2)
	print('Balsa') if s & 1 | k & 1 else print('Koca')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	arr = list((x % 3 for x in a))
	n1 = arr.count(1)
	n2 = arr.count(2)
	if n1 & 1 | n2 & 1:
		print('Balsa')
	else:
		print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	my012dict = {0: 0, 1: 0, 2: 0}
	for i in a:
		my012dict[i % 3] += 1
	if my012dict[1] % 2 == 0 and my012dict[2] % 2 == 0:
		print('Koca')
	else:
		print('Balsa')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	k = 0
	for i in range(n):
		k ^= a[i] % 3
	if k == 0:
		print('Koca')
	else:
		print('Balsa')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	new_arr = [x % 3 for x in arr]
	n_1 = new_arr.count(1)
	n_2 = new_arr.count(2)
	print('Balsa') if n_1 & 1 | n_2 & 1 else print('Koca')