Alice and Bob are playing a game on a sequence $a_1, a_2, \dots, a_n$ of length $n$. They move in turns and Alice moves first.

In the turn of each player, he or she should select an integer and remove it from the sequence. The game ends when there is no integer left in the sequence.

Alice wins if the sum of her selected integers is even; otherwise, Bob wins.

Your task is to determine who will win the game, if both players play optimally.


-----Input-----

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 100$), indicating the length of the sequence.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \leq a_i \leq 10^9$), indicating the elements of the sequence.


-----Output-----

For each test case, output "Alice" (without quotes) if Alice wins and "Bob" (without quotes) otherwise.


-----Examples-----

Input
4
3
1 3 5
4
1 3 5 7
4
1 2 3 4
4
10 20 30 40
Output
Alice
Alice
Bob
Alice


-----Note-----

In the first and second test cases, Alice always selects two odd numbers, so the sum of her selected numbers is always even. Therefore, Alice always wins.

In the third test case, Bob has a winning strategy that he always selects a number with the same parity as Alice selects in her last turn. Therefore, Bob always wins.

In the fourth test case, Alice always selects two even numbers, so the sum of her selected numbers is always even. Therefore, Alice always wins.

Difficulty: MEDIUM
Tags: Dynamic programming

Game theory

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odd = 0
	even = 0
	for x in a:
		if x % 2 == 0:
			even += 1
		else:
			odd += 1
	if even % 2 == 1 and odd % 4 != 2:
		print('Alice')
	elif even % 2 == 1:
		print('Bob')
	elif 1 <= odd % 4 <= 2:
		print('Bob')
	else:
		print('Alice')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odd = 0
	for i in a:
		if i % 2 == 1:
			odd += 1
	r = odd % 4
	if r == 0 or r == 3:
		print('Alice')
	elif r == 2:
		print('Bob')
	else:
		print('Alice' if n % 2 == 0 else 'Bob')


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	even = 0
	odd = 0
	for z in arr:
		if z % 2:
			odd += 1
	even = n - odd
	if odd % 2 == 0:
		if odd % 4 == 0:
			return 'Alice'
		return 'Bob'
	if odd % 4 == 3:
		return 'Alice'
	if even % 2:
		return 'Alice'
	return 'Bob'
for _ in range(int(input())):
	print(main())


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in a:
		if i % 2 == 1:
			ans += 1
	if ans % 4 in {0, 3}:
		print('Alice')
	elif ans % 4 == 1 and (n - ans) % 2 == 1:
		print('Alice')
	else:
		print('Bob')


import sys
readline = sys.stdin.readline

def ceil(A, B):
	return (A + B - 1) // B
T = int(readline())
for _ in range(T):
	N = int(readline())
	A = list(map(int, readline().split()))
	o = e = 0
	for a in A:
		if a % 2:
			o += 1
		else:
			e += 1
	odd = ceil(o, 2)
	even = ceil(e, 2)
	alice = ceil(N, 2)
	if alice == odd + even:
		if odd % 2 == 0:
			ans = 'Alice'
		else:
			ans = 'Bob'
	else:
		ans = 'Alice'
	print(ans)


def helper(o, e):
	if o % 4 in [0, 3]:
		return True
	return e % 4 in [1, 3] and o % 4 == 1
test = int(input())
for t in range(test):
	n = int(input())
	A = list(map(int, input().split()))
	e = 0
	o = 0
	for i in A:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	if helper(o, e):
		print('Alice')
	else:
		print('Bob')


def resolve(stones):
	evens_num = 0
	odds_num = 0
	for item in stones:
		if item % 2 == 1:
			odds_num += 1
		else:
			evens_num += 1
	case_id = odds_num % 4
	if case_id == 0:
		return True
	if case_id == 1:
		if evens_num % 2 == 0:
			return False
		else:
			return True
	if case_id == 2:
		return False
	if case_id == 3:
		return True

def read_input():
	lines_1 = input()
	lines_2 = input().split(' ')
	stones = []
	for item in lines_2:
		stones.append(int(item))
	return stones
case_num = int(input())
if not case_num == 0:
	for index in range(case_num):
		stones = read_input()
		res = resolve(stones)
		if res:
			print('Alice')
		else:
			print('Bob')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	for i in a:
		if i % 2 == 1:
			l += 1
	if n % 2 == 0 and l % 4 == 2 or (n % 2 == 1 and l % 4 == 1 or l % 4 == 2):
		print('Bob')
	else:
		print('Alice')


def IsAliceWin(EvenCount, OddCount):
	if OddCount % 4 in [0, 3]:
		return True
	return EvenCount % 4 in [1, 3] and OddCount % 4 == 1
for _ in range(int(input())):
	(EvenCount, OddCount) = [0, 0]
	input()
	for i in list(map(int, input().split())):
		if i % 2 == 0:
			EvenCount += 1
		else:
			OddCount += 1
	if IsAliceWin(EvenCount, OddCount):
		print('Alice')
	else:
		print('Bob')


def Alice(Even, Odd):
	if Odd % 4 in [0, 3]:
		return True
	return Even % 4 in [1, 3] and Odd % 4 == 1
for k in range(int(input())):
	input()
	(Even, Odd) = [0, 0]
	p = list(map(int, input().split()))
	for i in p:
		if i % 2 == 0:
			Even += 1
		else:
			Odd += 1
	if Alice(Even, Odd):
		print('Alice')
	else:
		print('Bob')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in a:
		if i % 2 == 1:
			c += 1
	c2 = n - c
	d = 0
	x = c // 2
	y = c2 // 2
	if c == 0:
		print('Alice')
	elif x % 2 == 1 and c % 2 == 1:
		print('Alice')
	elif x % 2 == 0 and (c % 2 == 0 or c2 % 2 == 1):
		print('Alice')
	else:
		print('Bob')


t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	S = [['A', 'B', 'B', 'A'], ['A', 'A', 'B', 'A'], ['A', 'B', 'B', 'A'], ['A', 'A', 'B', 'A']]
	odd = 0
	even = 0
	for el in A:
		if el % 2 == 0:
			even += 1
		else:
			odd += 1
	if S[even % 4][odd % 4] == 'A':
		print('Alice')
	else:
		print('Bob')


t = int(input())
for i in range(t):
	n0 = 0
	n1 = 0
	n = int(input())
	l0 = input().split()
	for k in l0:
		if int(k) % 2 == 0:
			n0 += 1
		else:
			n1 += 1
	if n1 % 4 == 2 or (n1 % 4 == 1 and n0 % 2 == 0):
		print('Bob')
	else:
		print('Alice')


def evenNumberAddicts(EvenSum, OddSum):
	if OddSum % 4 in [0, 3]:
		return True
	return EvenSum % 4 in [1, 3] and OddSum % 4 == 1
for _ in range(int(input())):
	(EvenSum, OddSum) = [0, 0]
	input()
	for i in list(map(int, input().split())):
		if i % 2 == 0:
			EvenSum += 1
		else:
			OddSum += 1
	if evenNumberAddicts(EvenSum, OddSum):
		print('Alice')
	else:
		print('Bob')


import math
t = int(input())
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	even = [i for i in a if i % 2 == 0]
	odd = [i for i in a if i % 2 == 1]
	o = len(odd)
	e = len(even)
	if o == 0:
		print('Alice')
	elif o == 1:
		if e % 2 == 1:
			print('Alice')
		else:
			print('Bob')
	elif o == 2:
		print('Bob')
	elif o % 2 == 1:
		if (o + 1) % 4 == 0:
			print('Alice')
		elif e % 2 == 0:
			print('Bob')
		else:
			print('Alice')
	elif o % 2 == 0:
		if o % 4 == 0:
			print('Alice')
		else:
			print('Bob')


from math import ceil
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = {0: 0, 1: 0}
	for i in a:
		if i % 2 == 0:
			f[0] += 1
		else:
			f[1] += 1
	if f[1] == 0:
		print('Alice')
	else:
		if n % 2 == 0:
			n = n // 2
		else:
			n = n // 2 + 1
		li = []
		if n % 2 == 0:
			k = n
		else:
			k = n - 1
		for i in range(0, k + 1, 2):
			li.append([n - i, i])
		flag = False
		for j in li:
			if j[0] <= ceil(f[0] / 2) and j[1] <= ceil(f[1] / 2):
				flag = True
				break
		if flag == True:
			print('Alice')
		else:
			print('Bob')


for _ in range(int(input().strip())):
	n = int(input().strip())
	l = list(map(int, input().split()))
	odd = 0
	for i in range(len(l)):
		if l[i] % 2:
			odd += 1
	c = odd % 4
	if c == 0 or c == 3:
		print('Alice')
	elif c == 2:
		print('Bob')
	else:
		print('Alice' if n % 2 == 0 else 'Bob')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if l[i] & 1:
			count += 1
	if count % 4 == 0 or count % 4 == 3:
		print('Alice')
	elif count % 4 == 2:
		print('Bob')
	elif n & 1:
		print('Bob')
	else:
		print('Alice')


for _ in range(int(input())):
	n = int(input())
	b = sum([*map(lambda x: int(x) % 2, input().split())])
	a = n - b
	print(['Alice', 'Bob'][b % 4 == 2 or not (b % 4 in [0, 3] or a % 2)])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	e = 0
	o = 0
	for j in range(n):
		if a[j] % 2 == 0:
			e += 1
		else:
			o += 1
	if o % 4 == 0:
		print('Alice')
	elif o % 4 == 2:
		print('Bob')
	elif o % 4 == 1:
		if e % 2 == 0:
			print('Bob')
		else:
			print('Alice')
	elif e % 2 == 0:
		print('Alice')
	elif (e + o) % 2 == 0:
		print('Alice')
	else:
		print('Bob')


t = int(input())
for i in range(t):
	n = int(input())
	seq = list(map(int, input().split()))
	oddseq = []
	evenseq = []
	for k in seq:
		if k % 2 == 0:
			evenseq.append(k)
		else:
			oddseq.append(k)
	even = len(evenseq)
	odd = len(oddseq)
	asum = 0
	bsum = 0
	if even % 2 == 0 and odd % 4 == 0:
		print('Alice')
	if even % 2 == 0 and odd % 4 == 1:
		print('Bob')
	if even % 2 == 0 and odd % 4 == 2:
		print('Bob')
	if even % 2 == 0 and odd % 4 == 3:
		print('Alice')
	if even % 2 == 1 and odd % 4 == 0:
		print('Alice')
	if even % 2 == 1 and odd % 4 == 1:
		print('Alice')
	if even % 2 == 1 and odd % 4 == 2:
		print('Bob')
	if even % 2 == 1 and odd % 4 == 3:
		print('Alice')


import os
import sys

def read_lines():
	filename = 'input.txt'
	if os.path.exists(filename):
		with open(filename, 'r') as f:
			lines = f.readlines()
	else:
		lines = sys.stdin.readlines()
	return [line.rstrip('\n') for line in lines]

def is_even(num):
	return num % 2 == 0

def is_odd(num):
	return not is_even(num)

def solve_case(input_case):
	input_array = [int(x) for x in input_case.split()]
	evens = 0
	odds = 0
	for i in input_array:
		if is_even(i):
			evens += 1
		else:
			odds += 1
	evens = evens % 2
	if odds % 4 == 0:
		print('Alice')
	elif odds % 4 == 3:
		print('Alice')
	elif odds % 4 == 2:
		print('Bob')
	elif odds % 4 == 1:
		if evens == 1:
			print('Alice')
		else:
			print('Bob')

def solve():
	lines = read_lines()
	for i in range(2, len(lines), 2):
		input_case = lines[i]
		solve_case(input_case)
solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(x, y) = (0, 0)
	for i in range(n):
		if a[i] % 2 == 0:
			x += 1
		else:
			y += 1
	if y % 4 == 2:
		print('Bob')
	elif y % 4 == 3:
		print('Alice')
	elif y % 4 == 0:
		print('Alice')
	elif x % 2 == 0:
		print('Bob')
	else:
		print('Alice')


import math
import _ast
n = int(input())
for i in range(n):
	m = int(input())
	even = 0
	uneven = 0
	subsequence = list(input().split())
	for i in subsequence:
		if int(i) % 2 == 0:
			even += 1
		else:
			uneven += 1
	if uneven % 4 == 2:
		print('Bob')
	elif uneven % 4 == 3 or uneven % 4 == 2 or uneven % 4 == 0:
		print('Alice')
	elif uneven % 2 == 1 and even % 2 == 1:
		print('Alice')
	else:
		print('Bob')


n = int(input())
for x in range(0, n):
	even = 0
	odd = 0
	m = int(input())
	numbers = input()
	elements = [int(num) for num in numbers.split(' ') if len(num) > 0]
	for y in range(0, m):
		if elements[y] % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd % 4 == 2:
		print('Bob')
	elif odd % 4 == 3:
		print('Alice')
	elif odd % 4 == 0:
		print('Alice')
	elif even % 2 == 1:
		print('Alice')
	else:
		print('Bob')


for asd in range(int(input())):
	n = int(input())
	items = [int(i) % 2 for i in input().split()]
	if (items.count(1) % 4 in [0, 3] or items.count(0) % 2 == 1) and items.count(1) % 4 != 2:
		print('Alice')
	else:
		print('Bob')


n = int(input())
x = []

class pointer:

	def __init__(self, list, k):
		self.list = list
		self.len = k
for i in range(n):
	(a, b) = (int(input()), input())
	b = b.split()
	x.append(pointer(b, a))
for i in x:
	odd = 0
	even = 0
	for j in range(i.len):
		if int(i.list[j]) % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd % 4 == 0 or odd % 4 == 3:
		print('Alice')
	else:
		if even % 2 == 0:
			odd += 1
		check = odd % 4
		if check <= 1:
			print('Alice')
		else:
			print('Bob')


t = int(input())
m = 1000000000.0 + 7

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	odd = 0
	even = 0
	for i in range(0, len(arr)):
		if arr[i] % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd % 4 == 2:
		print('Bob')
	elif odd % 4 == 0:
		print('Alice')
	elif odd % 4 == 3:
		print('Alice')
	elif even % 2 == 1:
		print('Alice')
	else:
		print('Bob')
for _ in range(t):
	solve()


t = int(input())
while t != 0:
	n = int(input())
	arr = list(map(int, input().split()))
	noOfOdds = 0
	noOfEvens = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			noOfEvens += 1
		else:
			noOfOdds += 1
	res = 'Bob'
	if noOfEvens == n and n > 0:
		res = 'Alice'
	elif noOfOdds > 0:
		if noOfOdds % 4 == 1:
			if noOfEvens % 2 != 0:
				res = 'Alice'
		elif noOfOdds % 4 == 2:
			res = 'Bob'
		elif noOfOdds % 4 == 3:
			res = 'Alice'
		else:
			res = 'Alice'
	t -= 1
	print(res)


t = int(input())
winners = ['Alice', 'Bob']
for _ in range(t):
	n = int(input())
	nums = [int(x) % 2 for x in input().split()]
	x = nums.count(0)
	y = nums.count(1)
	c = y % 4
	if x % 2 == 0:
		if c == 0 or c == 3:
			print(winners[0])
		else:
			print(winners[1])
	elif c == 0 or c == 1 or c == 3:
		print(winners[0])
	else:
		print(winners[1])


def even_num_addict(a):
	even = 0
	odd = 0
	dp_odd = [1, 2]
	dp_ev = [3, 4]
	d = {'Alice': [3, 4], 'Bob': [1, 2]}
	for i in a:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd % 4 == 0 or odd % 4 == 3 or (odd % 4 == 1 and len(a) % 2 == 0):
		return 'Alice'
	else:
		return 'Bob'
for _ in range(int(input())):
	n = input()
	a = [int(item) for item in input().split()]
	print(even_num_addict(a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(ii) for ii in input().split()]
	(a1, a2) = (0, 0)
	for i in a:
		if i % 2 == 0:
			a2 += 1
		else:
			a1 += 1
	if a1 == 0:
		print('Alice')
		continue
	if a2 == 0:
		if (n + 1) // 2 % 2 == 0:
			print('Alice')
		else:
			print('Bob')
		continue
	if n == 1:
		if a[0] % 2 == 0:
			print('Alice')
		else:
			print('Bob')
		continue
	if n == 2:
		if a[0] % 2 == 0 or a[1] % 2 == 0:
			print('Alice')
		else:
			print('Bob')
		continue
	if n == 3:
		if a2 == 0:
			print('Alice')
		else:
			print('Bob')
		continue
	if a1 % 4 == 0:
		print('Alice')
	elif a1 % 4 == 1:
		if a2 % 2 == 1:
			print('Alice')
		else:
			print('Bob')
	elif a1 % 4 == 2:
		print('Bob')
	else:
		print('Alice')


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	odd = 0
	even = 0
	for x in nums:
		if x % 2 == 1:
			odd += 1
		else:
			even += 1
	if odd % 4 == 0:
		print('Alice')
	elif odd % 4 == 1:
		if even % 2 == 1:
			print('Alice')
		else:
			print('Bob')
	elif odd % 4 == 2:
		print('Bob')
	else:
		print('Alice')


def sol():
	n = int(input())
	l = list(map(int, input().split()))
	(odd, even) = (0, 0)
	for i in l:
		if i & 1:
			odd += 1
		else:
			even += 1
	if odd % 4 == 0 or ((odd - 1) % 4 == 0 and n % 2 == 0) or (odd + 1) % 4 == 0:
		print('Alice')
	else:
		print('Bob')
t = int(input())
while t:
	sol()
	t -= 1


def pickodd(av):
	for i in range(len(av)):
		if av[i] % 2 != 0:
			ans = av.pop(i)
			return ans
	ans = av.pop()
	return ans

def pickeven(av):
	for i in range(len(av)):
		if av[i] % 2 == 0:
			ans = av.pop(i)
			return ans
	ans = av.pop()
	return ans
for i in range(int(input())):
	tn = int(input())
	l = [int(i) for i in input().split()]
	ec = 0
	oc = 0
	t = 'a'
	for i in l:
		if i % 2 == 0:
			ec += 1
		else:
			oc += 1
	oc = oc % 4
	s = 0
	av = [1 for i in range(oc)]
	if ec % 2 != 0:
		av = av + [2]
	while len(av) != 0:
		if t == 'a' and s % 2 != 0:
			s = s + pickodd(av)
			t = 'b'
		elif t == 'a' and s % 2 == 0:
			if oc > 1 and oc % 2 != 0:
				s = s + pickodd(av)
				t = 'b'
			else:
				s = s + pickeven(av)
				t = 'b'
		elif t == 'b' and s % 2 != 0:
			pickodd(av)
			t = 'a'
		elif t == 'b' and s % 2 == 0:
			pickeven(av)
			t = 'a'
		else:
			print('default something is missing')
	if s % 2 == 0:
		print('Alice')
	else:
		print('Bob')


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	ji = 0
	ou = 0
	for i in a:
		if i & 1:
			ji += 1
		else:
			ou += 1
	f = 0
	if ji % 4 == 2:
		f = 0
	elif ji % 4 in [0, 3]:
		f = 1
	elif ou & 1:
		f = 1
	if f:
		print('Alice')
	else:
		print('Bob')


for _ in range(int(input())):
	n = int(input())
	d = list(map(int, input().split()))
	Alice = False
	cnt = {1: 0, 0: 0}
	for i in d:
		cnt[i & 1] += 1
	cnt[1] %= 4
	cnt[0] %= 2
	if cnt[1] == 3 or cnt[1] == 0 or (cnt[1] == 1 and cnt[0] == 1):
		print('Alice')
	else:
		print('Bob')


tasks = int(input())
for t in range(tasks):
	n = int(input())
	a = list(map(int, input().split()))
	even = len([x for x in a if x % 2 == 0])
	odd = n - even
	result = 'Alice'
	if odd % 4 == 1 and even % 2 == 0 or odd % 4 == 2:
		result = 'Bob'
	print(result)


t = int(input())
for i in range(t):
	odds = 0
	evens = 0
	n = int(input())
	numbers = [int(s) for s in input().split()]
	for j in numbers:
		if j % 2 == 0:
			evens += 1
		else:
			odds += 1
	if odds == 0:
		print('Alice')
	elif odds % 4 == 1:
		if (odds + evens) % 2 == 0:
			print('Alice')
		else:
			print('Bob')
	elif odds % 4 == 2:
		print('Bob')
	elif odds % 4 == 3:
		print('Alice')
	elif odds % 4 == 0:
		print('Alice')


t = int(input())
for i in range(t):
	input()
	n = input().split(' ')
	nums = [int(strings) for strings in n]
	even = 0
	odd = 0
	for numbers in nums:
		if numbers % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd % 4 == 0:
		print('Alice')
	elif odd % 4 == 1:
		if (odd - even) % 2 == 1:
			print('Bob')
		else:
			print('Alice')
	elif odd % 4 == 2:
		print('Bob')
	else:
		print('Alice')


for i in range(int(input())):
	x = input()
	m = list(map(int, input().split()))
	even = [i for i in m if i % 2 == 0]
	odd = [i for i in m if i % 2]
	if len(even) % 2 == 0:
		if len(odd) % 4 == 0 or len(odd) % 4 == 3:
			print('Alice')
		else:
			print('Bob')
	elif len(odd) % 4 == 2:
		print('Bob')
	else:
		print('Alice')


def getint():
	return [int(i) for i in input().split()]

def get():
	return int(input())

def S():
	for test in range(int(input())):
		solve()

def solve():
	n = get()
	a = getint()
	ou = 0
	ji = 0
	for i in range(n):
		if a[i] % 2 == 0:
			ou += 1
		else:
			ji += 1
	if ou == n:
		print('Alice')
		return
	if n & 1:
		if ji % 4 == 1 or ji % 4 == 2:
			print('Bob')
		else:
			print('Alice')
	elif ji % 4 == 2:
		print('Bob')
	else:
		print('Alice')
S()


def solve(ecnt, ocnt):
	k = ocnt % 4
	p = ecnt % 4
	if k in [0, 3]:
		return True
	if p in [1, 3] and (k == 1) == True:
		return True
	else:
		return False
for z in range(int(input())):
	ecnt = 0
	ocnt = 0
	r = int(input())
	s = list(map(int, input().split()))
	for i in s:
		if i % 2 == 0:
			ecnt += 1
		else:
			ocnt += 1
	if solve(ecnt, ocnt):
		print('Alice')
	else:
		print('Bob')


t = int(input())
for i in range(t):
	n = int(input())
	xs = [int(x) for x in input().split()]
	count_odd = 0
	count_even = 0
	for s in xs:
		if s % 2 == 1:
			count_odd += 1
		else:
			count_even += 1
	if count_even % 2 == 0:
		if count_odd % 2 == 0:
			alice_odd = count_odd // 2
			if alice_odd % 2 == 0:
				print('Alice')
			else:
				print('Bob')
		else:
			alice_odd = (count_odd + 1) // 2
			if alice_odd % 2 == 0:
				print('Alice')
			else:
				print('Bob')
	elif count_odd % 2 == 0:
		alice_odd = count_odd // 2
		if alice_odd % 2 == 0:
			print('Alice')
		else:
			print('Bob')
	else:
		print('Alice')


import sys
dp = dict()

def bob(c0, c1, a):
	if c0 > 0:
		if c1 > 0:
			return not alice(c0 - 1, c1, a) or not alice(c0, c1 - 1, a)
		else:
			return not alice(c0 - 1, c1, a)
	elif c1 > 0:
		return not alice(c0, c1 - 1, a)
	else:
		return a != 0

def alice(c0, c1, a):
	if (c0, c1, a) in dp:
		return dp[c0, c1, a]
	if c0 > 0:
		if c1 > 0:
			r = not bob(c0 - 1, c1, a) or not bob(c0, c1 - 1, a ^ 1)
		else:
			r = not bob(c0 - 1, c1, a)
	elif c1 > 0:
		r = not bob(c0, c1 - 1, a ^ 1)
	else:
		r = a == 0
	dp[c0, c1, a] = r
	return r

def solve():
	inp = sys.stdin.readline
	n = map(int, inp().split())
	c = [0, 0]
	for i in map(int, inp().split()):
		c[i % 2] += 1
	if alice(c[0], c[1], 0):
		print('Alice')
	else:
		print('Bob')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_int():
	return int(input())

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	a = inp_arr()
	o = 0
	e = 0
	for x in a:
		if x % 2 == 1:
			o += 1
		else:
			e += 1
	if o % 4 == 0 or (o + 1) % 4 == 0 or (o % 2 == 1 and e % 2 == 1):
		print('Alice')
	else:
		print('Bob')
tt = inp_int()
for t in range(tt):
	solve()


for _ in range(int(input())):
	N = int(input())
	my_list = list(map(int, input().split()))
	odd = 0
	even = 0
	for num in my_list:
		if num % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd == 0:
		print('Alice')
	elif even == 0:
		if odd % 4 == 0 or odd % 4 == 3:
			print('Alice')
		else:
			print('Bob')
	elif odd % 2 != 0 and even % 2 != 0:
		print('Alice')
	elif odd % 4 == 0 or odd % 4 == 3:
		print('Alice')
	else:
		print('Bob')


import math
N = int(input())
h = []
for i in range(N):
	n = int(input())
	k0 = 0
	k1 = 0
	a = list(map(int, input().split()))
	for t in a:
		if t % 2 == 0:
			k0 = k0 + 1
		else:
			k1 = k1 + 1
	if k1 == 1:
		if n % 2 == 1:
			h.append('Bob')
		else:
			h.append('Alice')
	elif k1 == 0:
		h.append('Alice')
	elif k1 % 2 == 1:
		if math.ceil(k1 / 2) % 2 == 1 and n % 2 == 1:
			h.append('Bob')
		else:
			h.append('Alice')
	elif k1 % 2 == 0 and k1 % 4 != 0:
		h.append('Bob')
	else:
		h.append('Alice')
for t in h:
	print(t)


from math import ceil
for loop in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(ce, co) = (0, 0)
	for i in range(n):
		if a[i] % 2 == 0:
			ce += 1
		else:
			co += 1
	qo = co // 2 % 2
	ro = co % 2
	re = ce % 2
	if qo == 0:
		if ro == 1 and re == 0:
			print('Bob')
		else:
			print('Alice')
	else:
		if ro == 1 and re == 0 or (ro == 1 and re == 1):
			print('Alice')
		if ro == 0 and re == 1 or (ro == 0 and re == 0):
			print('Bob')


t = int(input())
for q in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	nc = 0
	for x in a:
		if x % 2 == 0:
			c += 1
		else:
			nc += 1
	if c % 2 == 1 and nc % 2 == 1:
		f = True
	elif c % 2 == 0 and nc % 2 == 0:
		if nc % 4 == 0:
			f = True
		else:
			f = False
	elif c % 2 == 0 and nc % 2 == 1:
		if nc % 4 == 3:
			f = True
		else:
			f = False
	elif nc % 4 == 0:
		f = True
	else:
		f = False
	if f:
		print('Alice')
	else:
		print('Bob')


from re import L
for _ in range(int(input())):
	a = int(input())
	b = [int(i) for i in input().split()]
	(even, odd) = (0, 0)
	for i in b:
		if i & 1:
			odd += 1
		else:
			even += 1
	if odd % 4 == 0:
		print('Alice')
	elif odd % 4 == 1:
		if even % 2:
			print('Alice')
		else:
			print('Bob')
	elif odd % 4 == 2:
		print('Bob')
	elif odd % 4 == 3:
		print('Alice')


for _ in range(int(input())):
	n = int(input())
	lis = [int(i) for i in input().split()]
	od = 0
	for i in lis:
		if i % 2:
			od += 1
	rem = od % 4
	if rem == 0 or rem == 3:
		print('Alice')
	elif rem == 2:
		print('Bob')
	elif n % 2 == 0:
		print('Alice')
	else:
		print('Bob')


from functools import cmp_to_key
from collections import Counter, deque, defaultdict, OrderedDict
import math
from bisect import bisect, bisect_left
import sys
import re
from copy import deepcopy
MOD = 10 ** 9 + 7
MAX = -sys.maxsize
MIN = sys.maxsize

class get:

	def int():
		return list(map(int, input().split()))

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

	def map():
		return map(int, input().split())

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def print2d(arr):
	for item in arr:
		print(*item)

def solve():
	n = int(input())
	a = get.int()
	n_even = n_odd = 0
	for i in a:
		if i % 2:
			n_odd += 1
		else:
			n_even += 1
	if n_odd % 4 == 2:
		print('Bob')
	elif n_odd % 4 == 3 or n_odd % 4 == 0:
		print('Alice')
	elif n_even % 2:
		print('Alice')
	else:
		print('Bob')
t = int(input())
for tt in range(t):
	solve()


for s in [*open(0)][2::2]:
	s = [*map(int, s.split())]
	o = 0
	for x in s:
		o += x & 1
	print(['Bob', 'Alice'][o % 4 == 0 or o % 4 == 3 or (o % 4 == 1 and len(s) % 2 == 0)])


def diginto(allmode, *cases):
	valid = list(filter(lambda x: False if x is None else True, cases))
	if valid:
		return all(valid) if allmode else any(valid)
	else:
		return None

def game(athand, lefteven, leftodd):
	if lefteven < 0 or leftodd < 0:
		return None
	if leftodd == 0:
		return athand
	if (athand, lefteven, leftodd) in gamecache:
		return gamecache[athand, lefteven, leftodd]
	else:
		takeodd = diginto(True, game(not athand, lefteven, leftodd - 2), game(not athand, lefteven - 1, leftodd - 1))
		takeeven = diginto(True, game(athand, lefteven - 1, leftodd - 1), game(athand, lefteven - 2, leftodd))
		gamecache[athand, lefteven, leftodd] = diginto(False, takeodd, takeeven)
		return gamecache[athand, lefteven, leftodd]
gamecache = {(True, 0, 0): True, (False, 0, 0): False, (True, 1, 0): True, (True, 0, 1): False, (False, 1, 0): False, (False, 0, 1): True}
num_of_cases = int(input())
for case in range(num_of_cases):
	n = int(input())
	odd = len(list(filter(lambda x: x % 2, map(int, input().split()))))
	even = n - odd
	if game(True, even, odd):
		print('Alice')
	else:
		print('Bob')


def devide(x):
	return x % 2
for i in range(int(input())):
	n = int(input())
	ori = map(int, input().split())
	lst = list(map(devide, ori))
	even = lst.count(0)
	odd = lst.count(1)
	if odd % 4 == 0:
		print('Alice')
	elif odd % 4 == 1:
		if even % 2 == 0:
			print('Bob')
		else:
			print('Alice')
	elif odd % 4 == 2:
		print('Bob')
	else:
		print('Alice')


x = int(input())
j = 0
ans = []

def funx():
	n = int(input())
	ai = input().split()
	ai = [int(x) for x in ai]
	even_a = [x for x in ai if x % 2 == 0]
	evens = len(even_a)
	odds = n - evens
	if odds % 4 == 2 and evens % 2 == 0:
		ans.append('Bob')
	elif odds % 4 == 1 and evens % 2 == 0:
		ans.append('Bob')
	elif odds % 4 == 2 and evens % 2 == 1:
		ans.append('Bob')
	else:
		ans.append('Alice')
for i in range(x):
	funx()
[print(i) for i in ans]


t = int(input())
for i in range(t):
	n = int(input())
	w = [int(k) for k in input().split()]
	(x, y) = (0, 0)
	for j in w:
		if j % 2 == 0:
			x += 1
		else:
			y += 1
	if y % 4 == 2 and x % 2 == 0:
		print('Bob')
	elif y % 4 == 3 and x % 2 == 0:
		print('Alice')
	elif y % 4 == 0 and x % 2 == 0:
		print('Alice')
	elif y % 4 == 1 and x % 2 == 0:
		print('Bob')
	elif y % 4 == 0 and x % 2 == 1:
		print('Alice')
	elif y % 4 == 2 and x % 2 == 1:
		print('Bob')
	elif y % 4 == 3 and x % 2 == 1:
		print('Alice')
	elif y % 4 == 1 and x % 2 == 1:
		print('Alice')


def solve(A):
	odd = 0
	even = 0
	for i in A:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd == 0:
		return True
	odd = odd % 4
	if even == 0:
		if odd == 0 or odd == 3:
			return True
		else:
			return False
	even = even % 2
	if odd == 0:
		return True
	if odd == 1:
		if even == 0:
			return False
		return True
	if odd == 2:
		return False
	if odd == 3:
		return True
N = int(input())
for _ in range(N):
	n = int(input())
	A = [int(x) for x in input().split(' ')]
	if solve(A):
		print('Alice')
	else:
		print('Bob')


import sys

def read_int():
	return int(sys.stdin.readline())

def read_iarray():
	return [int(i) for i in sys.stdin.readline().strip().split()]

def solve(ne, no, ac):
	if no == 0 and ne == 0:
		return not ac
	if no == 0 and ne == 1:
		return not ac
	if no == 1:
		return ac or ne == 1
	return solve(ne, no - 2, not ac)
t = read_int()
for _ in range(t):
	n = read_int()
	nums = read_iarray()
	(ne, no, tot) = (0, 0, len(nums))
	for n in nums:
		if n % 2 == 0:
			ne += 1
		else:
			no += 1
	print('Alice' if solve(ne % 2, no, False) else 'Bob')


def k(ec, oc):
	if oc % 4 in [0, 3]:
		return True
	return ec % 4 in [1, 3] and oc % 4 == 1
t = int(input())
for i in range(t):
	(ec, oc) = [0, 0]
	input()
	for i in list(map(int, input().split())):
		if i % 2 == 0:
			ec = ec + 1
		else:
			oc = oc + 1
	if k(ec, oc):
		print('Alice')
	else:
		print('Bob')


t = int(input())
N = 120
dp = [[[False, False] for j in range(N)] for i in range(N)]
for i in range(N):
	if (i + 1) // 2 % 2 == 0:
		dp[0][i][0] = True
		dp[0][i][1] = False
	else:
		dp[0][i][0] = False
		dp[0][i][1] = True
	dp[i][0][0] = True
	dp[i][0][1] = False
for i in range(1, N):
	for j in range(1, N):
		for k in range(2):
			if (j == 0 or dp[i - 1][j - 1][k]) and (i == 1 or dp[i - 2][j][k]):
				dp[i][j][k] = True
			if (j == 1 or dp[i][j - 2][1 - k]) and (j == 0 or dp[i - 1][j - 1][1 - k]):
				dp[i][j][k] = True
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(i, j) = (0, 0)
	for x in a:
		if x % 2:
			j += 1
		else:
			i += 1
	if dp[i][j][0]:
		print('Alice')
	else:
		print('Bob')


from codecs import BOM_BE
from collections import Counter, defaultdict, deque
from re import L
import sys, threading
from tkinter import E
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
t = inp()
for _ in range(t):
	n = inp()
	nums = inlt()
	oddCount = 0
	evenCount = 0
	for num in nums:
		oddCount += num % 2
		evenCount += 1 - num % 2
	if oddCount % 2 and evenCount % 2:
		print('Alice')
	elif oddCount % 2 == 0 and evenCount % 2 == 0:
		if oddCount // 2 % 2:
			print('Bob')
		else:
			print('Alice')
	elif oddCount % 2 == 0 and evenCount % 2:
		if oddCount // 2 % 2:
			print('Bob')
		else:
			print('Alice')
	elif oddCount % 2 and evenCount % 2 == 0:
		if (oddCount // 2 + 1) % 2 == 0:
			print('Alice')
		else:
			print('Bob')


def one():
	n = int(input())
	t = list(map(int, input().split()))
	o = sum((x % 2 for x in t))
	e = n - o
	dp = [[[None, None] for i in range(o + 1)] for j in range(e + 1)]
	dp[0][0] = [True, False]

	def possible(dp, e, o):
		if dp[e][o] == [None, None]:
			if o == 0:
				p = possible(dp, e - 1, o)
				dp[e][o][0] = not p[1]
				dp[e][o][1] = not p[0]
			elif e == 0:
				q = possible(dp, e, o - 1)
				dp[e][o][0] = not q[1 - o % 2]
				dp[e][o][1] = not q[o % 2]
			else:
				p = possible(dp, e - 1, o)
				q = possible(dp, e, o - 1)
				dp[e][o][0] = not p[1 - o % 2] or not q[1 - o % 2]
				dp[e][o][1] = not p[o % 2] or not q[o % 2]
		return dp[e][o]
	r = possible(dp, e, o)
	return r[0]
t = int(input())
for i in range(t):
	print('Alice' if one() else 'Bob')


import sys
input = lambda : sys.stdin.readline().rstrip()
import math
from functools import lru_cache
t = int(input())

@lru_cache(None)
def payout(x, y, z, n):
	if x == n:
		if y % 2 == 0:
			return 1
		else:
			return 0
	elif x % 2 == 0:
		if z == 0:
			return payout(x + 1, y, z, n)
		elif z == n - x:
			return payout(x + 1, y + 1, z - 1, n)
		else:
			return max(payout(x + 1, y, z, n), payout(x + 1, y + 1, z - 1, n))
	elif z == 0:
		return payout(x + 1, y, z, n)
	else:
		(a, b) = (payout(x + 1, y, z, n), payout(x + 1, y, z - 1, n))
		if z == n - x:
			return b
		else:
			return min(a, b)
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(len(arr)):
		arr[i] = arr[i] % 2
	s = sum(arr)
	ans = payout(0, 0, s, n)
	if ans == 1:
		print('Alice')
	else:
		print('Bob')