There are $N$ piles of stones where the ith pile has $x_i$ stones in it. Alice and Bob play the following game:

Alice starts, and they alternate turns.

In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the newly created piles have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: $(1,2,5),(1,3,4),(1,7),(2,6)$ or $(3,5)$. 

The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

Given the starting set of piles, who wins the game assuming both players play optimally (that means they will not make a move that causes them to lose the game if some better, winning move exists)?

Input Format

The first line contains the number of test cases $\mathbf{T}$. $\mathbf{T}$ test cases follow. The first line for each test case contains $N$, the number of piles initially. The next line contains $N$ space delimited numbers, the number of stones in each of the piles.

Constraints

$1<=T<=50$
$1<=N<=50$  
$1<=x_i<=50$

Output Format

Output $\mathbf{T}$ lines, one corresponding to each test case containing ALICE if Alice wins the game and BOB otherwise.

Sample Input
4  
1  
4  
2  
1 2  
3  
1 3 4  
1  
8

Sample Output
BOB  
BOB  
ALICE  
BOB

Explanation

For the first case, the only possible move for Alice is (4) -> (1,3). Now Bob breaks up the pile with 3 stones into (1,2). At this point Alice cannot make any move and has lost.

Difficulty: MEDIUM_HARD
Tags: Game theory

Starter code:

Solutions:
from collections import Counter
ncases = int(input())
ndigs = [0, 1]
while len(ndigs) <= 50:
	ndigs += [ndigs[-1] + 1] * len(ndigs)
losers = set([1, 2, 4, 8])
for _ in range(ncases):
	npiles = int(input())
	ctr = Counter((int(f) for f in input().split()))
	total = 0
	for (size, count) in ctr.items():
		if size not in losers and count & 1 != 0:
			total ^= size - min(4, ndigs[size])
	print('ALICE' if total != 0 else 'BOB')


from functools import reduce
import operator

def partition2(number, thr):
	answer = set()
	if number < thr:
		answer.add((number,))
	for x in range(1, min(thr, number)):
		for y in partition2(number - x, x):
			answer.add(tuple(sorted((x,) + y)))
	return answer

def mex(a):
	res = 0
	while res in a:
		res += 1
	return res
heap_table = {1: 0, 2: 0}
for n in range(3, 51):
	numbers = set()
	for partition in partition2(n, n):
		partition = map(lambda x: heap_table[x], partition)
		number = reduce(operator.xor, partition)
		numbers.add(number)
	heap_table[n] = mex(numbers)
T = int(input())
for t in range(T):
	N = int(input())
	piles = list(map(int, input().split()))
	piles = map(lambda x: heap_table[x], piles)
	res = reduce(operator.xor, piles)
	print('ALICE' if res else 'BOB')


spaceGrundy = {0: 0, 1: 0, 2: 0, 3: 1, 4: 0, 5: 2, 6: 3, 7: 4, 8: 0, 9: 5, 10: 6, 11: 7, 12: 8, 13: 9, 14: 10, 15: 11, 16: 12, 17: 13, 18: 14, 19: 15, 20: 16, 21: 17, 22: 18, 23: 19, 24: 20, 25: 21, 26: 22, 27: 23, 28: 24, 29: 25, 30: 26, 31: 27, 32: 28, 33: 29, 34: 30, 35: 31, 36: 32, 37: 33, 38: 34, 39: 35, 40: 36, 41: 37, 42: 38, 43: 39, 44: 40, 45: 41, 46: 42, 47: 43, 48: 44, 49: 45, 50: 46}

def xor(game):
	temp = 0
	for x in game:
		temp ^= x
	return temp
for _ in range(int(input())):
	n = int(input())
	game = [int(x) for x in input().split()]
	if xor([spaceGrundy[a] for a in game]) == 0:
		print('BOB')
	else:
		print('ALICE')


(ways, Grundy) = ([], [])

def xor(a):
	x = 0
	for i in a:
		x ^= Grundy[i]
	return x
for i in range(51):
	ways.append(set())
	for j in range(1, i + 1 >> 1):
		ways[-1].add((j, i - j))
		for k in filter(lambda x: all((y > j for y in x)), ways[i - j]):
			ways[-1].add((j,) + k)
	g = set()
	for j in ways[i]:
		g.add(xor(j))
	j = 0
	while j in g:
		j += 1
	Grundy.append(j)
for _ in range(int(input())):
	input()
	print('ALICE' if xor(map(int, input().split())) else 'BOB')


import sys
import math
numbers = [-1, 0, 0, 1, 0, 2, 3, 4, 0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46]

def grundy(A):
	val = numbers[A[0]]
	for i in range(1, len(A)):
		val = val ^ numbers[A[i]]
	print('BOB' if val == 0 else 'ALICE')
T = int(input().strip())
for t in range(T):
	N = int(input())
	A = [int(i) for i in input().strip().split()]
	grundy(A)


def SG(n):
	if n <= 8:
		return [0, 0, 0, 1, 0, 2, 3, 4, 0][n]
	return n - 4
for t in range(int(input())):
	n = int(input())
	nim_sum = 0
	for x_i in list(map(int, input().split())):
		nim_sum ^= SG(x_i)
	print(['BOB', 'ALICE'][nim_sum > 0])


from functools import reduce
gr = [0, 0, 0, 1, 0, 2, 3, 4, 0]

def g(n):
	if n <= 8:
		return gr[n]
	else:
		return n - 4
t = int(input())
for _ in range(t):
	n = int(input())
	l = [g(int(i)) for i in input().split()]
	temp = reduce(lambda x, y: x ^ y, l)
	if temp == 0:
		print('BOB')
	else:
		print('ALICE')


import itertools
import functools
import operator

@functools.lru_cache(maxsize=None)
def partition(n):
	if n == 1:
		return [(1,)]
	res = [(n,)]
	for i in range(1, n):
		for p in partition(n - i):
			if i > p[-1]:
				res.append(p + (i,))
	return tuple(res)

@functools.lru_cache(maxsize=None)
def comp_sprague_grundy(n):
	if n <= 2:
		return 0
	positions = set()
	for p in partition(n):
		if len(p) == 1:
			continue
		positions.add(functools.reduce(operator.xor, (comp_sprague_grundy(x) for x in p)))
	mex = next((i for i in itertools.count() if i not in positions))
	return mex
for t_ in range(int(input())):
	n = int(input())
	grundy = functools.reduce(operator.xor, map(comp_sprague_grundy, map(int, input().split())))
	print('ALICE' if grundy else 'BOB')


grundy = [0, 0, 0, 1, 0, 2, 3, 4, 0, 5, 6, 7, 8, 9, 10]

def g(n):
	if n > 12:
		return n - 4
	else:
		return grundy[n]
tc = int(input())
for tcidx in range(tc):
	x = 0
	n = int(input())
	a = [g(int(x)) for x in input().split()]
	for b in a:
		x = x ^ b
	print('BOB' if x == 0 else 'ALICE')


import math
g = [0]

def mex(s):
	m = 0
	while m in s:
		m += 1
	return m

def find_splits(n, a):
	splits = []
	for i in range(a, math.ceil(n / 2)):
		splits.append([i, n - i])
		splits += list(map(lambda x: [i] + x, find_splits(n - i, i + 1)))
	return splits

def find_g(n):
	splits = find_splits(n, 1)
	s = set()
	for spl in splits:
		g_val = 0
		for i in spl:
			g_val ^= g[i]
		s.add(g_val)
	res = mex(s)
	g.append(res)
	return res
for i in range(1, 51):
	find_g(i)
for t in range(int(input())):
	N = int(input())
	piles = list(map(int, input().split()))
	g_val = 0
	for p in piles:
		g_val ^= g[p]
	print('ALICE' if g_val else 'BOB')


from functools import reduce
g = [0, 0, 0, 1, 0, 2, 3, 4, 0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46]
for _ in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	print('ALICE' if reduce(lambda x, y: x ^ y, map(lambda x: g[x], a)) > 0 else 'BOB')


(ways, Grundy) = ([], [])

def xor(a):
	x = 0
	for i in a:
		x ^= Grundy[i]
	return x
for i in range(51):
	ways.append(set())
	for j in range(1, i + 1 >> 1):
		ways[-1].add((j, i - j))
		for k in filter(lambda x: all((y > j for y in x)), ways[i - j]):
			ways[-1].add((j,) + k)
	g = set()
	for j in ways[i]:
		g.add(xor(j))
	j = 0
	while j in g:
		j += 1
	Grundy.append(j)
for _ in range(int(input())):
	input()
	print('ALICE' if xor(map(int, input().split())) else 'BOB')


from collections import Counter
ncases = int(input())
ndigs = [0, 1]
while len(ndigs) <= 50:
	ndigs += [ndigs[-1] + 1] * len(ndigs)
losers = set([1, 2, 4, 8])
for _ in range(ncases):
	npiles = int(input())
	ctr = Counter((int(f) for f in input().split()))
	total = 0
	for (size, count) in ctr.items():
		if size not in losers and count & 1 != 0:
			total ^= size - min(4, ndigs[size])
	print('ALICE' if total != 0 else 'BOB')


from collections import Counter
ncases = int(input())
ndigs = [0, 1]
while len(ndigs) <= 50:
	ndigs += [ndigs[-1] + 1] * len(ndigs)
losers = set([1, 2, 4, 8])
for _ in range(ncases):
	npiles = int(input())
	ctr = Counter((int(f) for f in input().split()))
	total = 0
	for (size, count) in ctr.items():
		if size not in losers and count & 1 != 0:
			total ^= size - min(4, ndigs[size])
	print('ALICE' if total != 0 else 'BOB')


import math

def recursive_break(G, i, L, S, N):
	if S == i:
		if len(L) == 1:
			return
		ans = 0
		for V in L:
			ans ^= G[V]
		if ans not in N:
			N[ans] = 1
		return
	st = 1 if len(L) == 0 else L[-1] + 1
	for j in range(st, i - S + 1):
		L.append(j)
		recursive_break(G, i, L, S + j, N)
		L.pop()
G = [-1] * 51
G[1] = 0
G[2] = 0
for i in range(3, 51):
	N = {}
	recursive_break(G, i, [], 0, N)
	N = list(N.keys())
	N.sort()
	cnt = 0
	for j in range(len(N)):
		if cnt != N[j]:
			break
		cnt += 1
	G[i] = cnt
T = int(input())
for _ in range(T):
	N = int(input())
	V = list(map(int, input().strip().split(' ')))
	ans = 0
	for E in V:
		ans ^= G[E]
	if ans == 0:
		print('BOB')
	else:
		print('ALICE')


from collections import Counter
ncases = int(input())
ndigs = [0, 1]
while len(ndigs) <= 50:
	ndigs += [ndigs[-1] + 1] * len(ndigs)
losers = set([1, 2, 4, 8])
for _ in range(ncases):
	npiles = int(input())
	ctr = Counter((int(f) for f in input().split()))
	total = 0
	for (size, count) in ctr.items():
		if size not in losers and count & 1 != 0:
			total ^= size - min(4, ndigs[size])
	print('ALICE' if total != 0 else 'BOB')


from collections import Counter
ncases = int(input())
ndigs = [0, 1]
while len(ndigs) <= 50:
	ndigs += [ndigs[-1] + 1] * len(ndigs)
losers = set([1, 2, 4, 8])
for _ in range(ncases):
	npiles = int(input())
	ctr = Counter((int(f) for f in input().split()))
	total = 0
	for (size, count) in ctr.items():
		if size not in losers and count & 1 != 0:
			total ^= size - min(4, ndigs[size])
	print('ALICE' if total != 0 else 'BOB')


from collections import Counter
ncases = int(input())
ndigs = [0, 1]
while len(ndigs) <= 50:
	ndigs += [ndigs[-1] + 1] * len(ndigs)
losers = set([1, 2, 4, 8])
for _ in range(ncases):
	npiles = int(input())
	ctr = Counter((int(f) for f in input().split()))
	total = 0
	for (size, count) in ctr.items():
		if size not in losers and count & 1 != 0:
			total ^= size - min(4, ndigs[size])
	print('ALICE' if total != 0 else 'BOB')