Alice and Bob are playing a game on a binary string S of length N.

Alice and Bob alternate turns, with Alice going first. On their turn, the current player must choose any index 1 ≤ i < |S| such that S_{i} \neq S_{i+1} and erase either S_{i} or S_{i+1} from the string. This reduces the length of S by one, and the remaining parts of S are concatenated in the same order.

The player who is unable to make a move loses.

Determine the winner if both players play optimally.

------ Input Format ------ 

- The first line of 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 a single integer N, the length of the string.
- The second line contains the binary string S of length N.

------ Output Format ------ 

For each test case output Alice if Alice wins the game, otherwise output Bob.
The output is not case-sensitive, so for example "Bob", "boB" and "Bob" are all considered equivalent.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$S$ is a binary string
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
1111
3
110
4
1010

----- Sample Output 1 ------ 
Bob
Alice
Bob
----- explanation 1 ------ 
Test Case $1$: There is no such index $i$ such that $S_{i} \neq S_{i+1}$. So, Alice does not have any move and loses, making Bob the winner.

Test Case $2$: Alice can choose $i=2$ (because $S_{2} = 1$ and $S_{3} = 0$) and remove $S_{3}$. After this move, the remaining string is "$11$". Bob now has no moves and thus loses.

Difficulty: HARD
Tags: String algorithms

Data structures

Game theory

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	N = int(input())
	S = input()
	C = 0
	C1 = 0
	for j in S:
		if j == '0':
			C += 1
		else:
			C1 += 1
	if min(C, C1) == 0:
		print('Bob', end='\n')
		continue
	if min(C, C1) == 1:
		print('Alice', end='\n')
		continue
	if N % 2:
		print('Alice', end='\n')
	else:
		print('Bob', end='\n')


for _ in range(int(input())):
	n = int(input())
	s = input()
	mini = min(s.count('1'), s.count('0'))
	if mini == 0:
		print('Bob')
	elif mini == 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


t = int(input())
while t >= 1:
	t -= 1
	n = int(input())
	s = str(input())
	c_0 = 0
	c_1 = 0
	for i in range(n):
		if s[i] == '1':
			c_0 += 1
		else:
			c_1 += 1
	if c_0 == 0 or c_1 == 0:
		print('Bob')
	elif c_0 == 1 or c_1 == 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


for _ in range(int(input())):
	n = int(input())
	s = input()
	zeros = s.count('0')
	ones = n - zeros
	if zeros == 0 or ones == 0:
		print('Bob')
		continue
	if n % 2 == 1:
		print('Alice')
	elif ones == 1 or zeros == 1:
		print('Alice')
	else:
		print('Bob')


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array
import collections
from math import ceil

def solve():

	def Bob():
		print('Bob')

	def Alice():
		print('Alice')
	for _ in range(*maps()):
		(n,) = maps()
		s = input()
		c0 = c1 = 0
		for i in s:
			if i == '0':
				c0 += 1
			else:
				c1 += 1
		x = min(c0, c1)
		if x == 0:
			Bob()
		elif x == 1:
			Alice()
		else:
			Bob() if n % 2 == 0 else Alice()

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')
solve()


for _ in range(int(input())):
	n = int(input())
	strg = input()
	zr = strg.count('0')
	onz = strg.count('1')
	if zr == 0 or onz == 0:
		print('Bob')
	elif zr == 1 or onz == 1:
		print('Alice')
	else:
		print('Alice') if n % 2 else print('Bob')


t = int(input())
for _ in range(t):
	x = int(input())
	y = input()
	(ones, zeros) = (y.count('1'), y.count('0'))
	if ones == 0 or zeros == 0:
		print('Bob')
	elif ones == 1 or zeros == 1:
		print('Alice')
	elif x % 2 == 0:
		print('Bob')
	else:
		print('Alice')


for _ in range(int(input())):
	n = int(input())
	l = [0, 0]
	s = input()
	for i in s:
		if i == '0':
			l[0] += 1
		else:
			l[1] += 1
	if l[0] == 0 or l[1] == 0:
		print('Bob')
	elif 1 in l:
		print('Alice')
	elif len(s) % 2 == 0:
		print('Bob')
	else:
		print('Alice')


for _ in range(int(input())):
	n = int(input())
	st = input()
	one_cnt = st.count('1')
	zero_cnt = n - one_cnt
	min_cnt = min(one_cnt, zero_cnt)
	if min_cnt == 0:
		print('Bob')
	elif min_cnt == 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


for _ in range(int(input())):
	n = int(input())
	a = input()
	cnt0 = a.count('1')
	cnt1 = n - cnt0
	if cnt1 == 0 or cnt0 == 0:
		print('Bob')
	elif cnt1 == 1 or cnt0 == 1:
		print('Alice')
	elif n % 2:
		print('Alice')
	else:
		print('Bob')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if s.count('1') == n or s.count('1') == 0:
		print('Bob')
	elif s.count('1') == 1 or s.count('1') == n - 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


for _ in range(int(input())):
	n = int(input())
	s = input()
	count_of_1 = s.count('1')
	count_of_0 = len(s) - count_of_1
	if count_of_1 == 0 or count_of_0 == 0:
		print('Bob')
	elif count_of_0 == 1 or count_of_1 == 1:
		print('Alice')
	elif len(s) % 2 == 0:
		print('Bob')
	else:
		print('Alice')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	t = min(s.count('0'), s.count('1'))
	if t == 0:
		print('Bob')
	elif t == 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


for _ in range(int(input())):
	res = ''
	n = int(input())
	x = input()
	one = x.count('1')
	zero = n - one
	if zero == n or one == n:
		res = 'Bob'
	elif zero == n - 1 or one == n - 1:
		res = 'Alice'
	elif abs(zero - one) % 2 == 0:
		res = 'Bob'
	else:
		res = 'Alice'
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	zero = s.count('0')
	ones = s.count('1')
	if zero == 1 or ones == 1:
		print('Alice')
		continue
	elif zero == 0 or ones == 0:
		print('Bob')
		continue
	x = n - 4
	if x & 1:
		print('Alice')
	else:
		print('Bob')


tcs = int(input())
for tc in range(tcs):
	flagg = 1
	n = int(input())
	w1 = input()
	co0 = w1.count('0')
	co1 = w1.count('1')
	if not min(co0, co1):
		flagg = 0
	if min(co0, co1) >= 2:
		mov = co0 + co1 - 2 * min(co0, co1)
		if not mov % 2:
			flagg = 0
	print('Alice' if flagg else 'Bob')


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('1')
	b = n - a
	if a == 0 or b == 0:
		print('Bob')
	elif a == 1 or b == 1:
		print('Alice')
	elif n & 1:
		print('Alice')
	else:
		print('Bob')


for _ in range(int(input())):
	l = int(input())
	no = input()
	ones = no.count('1')
	zeroes = no.count('0')
	if l == 1 or l == 0:
		print('Bob')
	elif ones == 1 or zeroes == 1:
		print('Alice')
	elif ones == 0 or zeroes == 0:
		print('Bob')
	elif ones % 2 == 0 and zeroes % 2 != 0 or (ones % 2 != 0 and zeroes % 2 == 0):
		print('Alice')
	else:
		print('Bob')


def solve(n, s):
	k = s.count('1')
	if k == 1 or n - k == 1:
		return 'Alice'
	if k == 0 or k == n:
		return 'Bob'
	if n % 2 == 0:
		return 'Bob'
	return 'Alice'
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(solve(n, s))


def solution():
	pass
for _ in range(int(input())):
	n = int(input())
	s = input()
	z = 0
	o = 0
	for i in s:
		if i == '1':
			o += 1
		else:
			z += 1
	if min(z, o) == 0:
		print('Bob')
	elif min(z, o) == 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


tests = int(input())
for _ in range(tests):
	n = int(input())
	s = input()
	c0 = 0
	c1 = 0
	for c in s:
		if c == '0':
			c0 += 1
		else:
			c1 += 1
	if min(c0, c1) == 0:
		print('Bob')
	elif min(c0, c1) == 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


for i in range(int(input())):
	n = int(input())
	s = input()
	c0 = 0
	c1 = 0
	for i in range(n):
		if s[i] == '0':
			c0 += 1
		else:
			c1 += 1
	if min(c1, c0) == 0:
		print('Bob')
	elif min(c1, c0) == 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


for _ in range(int(input())):
	n = int(input())
	s = input()
	on = 0
	zn = 0
	for i in s:
		if i == '0':
			zn += 1
		else:
			on += 1
	if zn == n or on == n:
		print('Bob')
	elif zn == 1 or on == 1:
		print('Alice')
	elif n % 2 != 0:
		print('Alice')
	else:
		print('Bob')


for _ in range(int(input())):
	N = int(input())
	string = list(input())
	cnt0 = string.count('0')
	cnt1 = string.count('1')
	if min(cnt1, cnt0) == 0:
		print('Bob')
	elif min(cnt1, cnt0) == 1:
		print('Alice')
	elif N % 2:
		print('Alice')
	else:
		print('Bob')


t = int(input())
for i in range(t):
	n = int(input())
	string = input()
	count1 = 0
	count0 = 0
	for i in string:
		if i == '1':
			count1 += 1
		else:
			count0 += 1
	if min(count0, count1) == 0:
		print('Bob')
	elif min(count1, count0) == 1:
		print('Alice')
	elif len(string) % 2:
		print('Alice')
	else:
		print('Bob')


import sys
from bisect import bisect
from math import sqrt, ceil, floor

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(1000000000.0) + 7
for _ in range(iinput()):
	n = iinput()
	s = input()
	zero = s.count('0')
	ones = n - zero
	if zero == 0 or ones == 0:
		ans = 'Bob'
	elif zero == 1 or ones == 1:
		ans = 'Alice'
	elif n % 2 == 0:
		ans = 'Bob'
	else:
		ans = 'Alice'
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	check = 1
	zero = ones = 0
	for i in s:
		if i == '0':
			zero += 1
		else:
			ones += 1
	if zero == len(s) or ones == len(s):
		check = 0
	if min(zero, ones) >= 2:
		res = zero + ones - 2 * min(zero, ones)
		if res % 2 == 0:
			check = 0
	if check == 1:
		print('Alice')
	else:
		print('Bob')


for i in range(int(input())):
	n = int(input())
	s = input()
	(turn, ones, zeroes) = (0, 0, 0)
	l = []
	zeroes = s.count('0')
	ones = s.count('1')
	if ones == 1 and zeroes == n - 1 or (ones == n - 1 and zeroes == 1):
		print('Alice')
	elif ones == 0 or zeroes == 0:
		print('Bob')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	c = Counter(s)
	if c['0'] == n or c['0'] == 0:
		ans = 'Bob'
	elif c['0'] == 1 or c['1'] == 1:
		ans = 'Alice'
	elif n % 2 == 0:
		ans = 'Bob'
	else:
		ans = 'Alice'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	(zero, ones) = (s.count('0'), s.count('1'))
	if zero == 1 or ones == 1:
		print('Alice')
	elif zero == 0 or ones == 0:
		print('Bob')
	elif n - 4 & 1:
		print('Alice')
	else:
		print('Bob')


t = int(input())
for T in range(t):
	n = int(input())
	string = input()
	ones = 0
	zeros = 0
	for ch in string:
		if ch == '1':
			ones += 1
		else:
			zeros += 1
	if ones == n or zeros == n:
		print('Bob')
	elif ones == 1 or zeros == 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


import sys
input = sys.stdin.readline
from math import ceil, floor, sqrt, gcd, log
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip('\r\n')

def solve():
	n = ri()
	s = rs()
	ans = 'Alice'
	z = o = 0
	for i in range(n):
		if s[i] == '1':
			o += 1
		else:
			z += 1
	(MIN, MAX) = (min(z, o), max(z, o))
	if MIN == 0:
		return 'Bob'
	if MIN == 1:
		return ans
	if n % 2 == 0:
		return 'Bob'
	return ans
for _ in range(ri()):
	print(solve())


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	c = s.count('0')
	if min(c, n - c) == 1:
		print('Alice')
	elif min(c, n - c) == 0:
		print('Bob')
	elif n & 1 == 1:
		print('Alice')
	else:
		print('Bob')


for _ in range(int(input())):
	n = int(input())
	s = input()
	x = s.count('1')
	y = s.count('0')
	if x == 0 or y == 0:
		print('Bob')
	elif min(x, y) == 1:
		print('Alice')
	elif abs(x - y) % 2 == 0:
		print('Bob')
	else:
		print('Alice')


from collections import Counter
from sys import stdin
input = stdin.readline

def func():
	freq = Counter(s)
	if freq['0'] == 0 or freq['1'] == 0:
		print('Bob')
		return
	if freq['0'] == 1 or freq['1'] == 1:
		print('Alice')
		return
	print('Alice' if (freq['0'] + freq['1']) % 2 != 0 else 'Bob')
for _ in range(int(input())):
	n = int(input())
	s = list(input().rstrip())
	func()


for _ in range(int(input())):
	n = int(input())
	a = list(input())
	c0 = a.count('0')
	c1 = n - c0
	if min(c1, c0) == 0:
		print('Bob')
		continue
	if min(c1, c0) == 1:
		print('Alice')
		continue
	if abs(c1 - c0) % 2 == 0:
		print('Bob')
	else:
		print('Alice')


t = int(input())
for tt in range(t):
	n = int(input())
	string = str(input())
	(c0, c1) = (0, 0)
	for i in string:
		if i == '0':
			c0 += 1
		else:
			c1 += 1
	if (c0 == 0) | (c1 == 0):
		print('Bob')
	elif min(c0, c1) == 1:
		print('Alice')
	elif n % 2 == 1:
		print('Alice')
	else:
		print('Bob')


try:
	for _ in range(int(input())):
		n = int(input())
		s = input()
		(ones, zeroes) = (0, 0)
		for i in s:
			if i == '1':
				ones += 1
			else:
				zeroes += 1
		if min(ones, zeroes) == 0:
			print('Bob')
		elif min(ones, zeroes) == 1:
			print('Alice')
		elif n % 2 == 1:
			print('Alice')
		else:
			print('Bob')
except:
	pass


n = int(input())
for i in range(n):
	l = int(input())
	s = input()
	ones = 0
	zeros = 0
	for i in s:
		if i == '1':
			ones += 1
		else:
			zeros += 1
	if l == ones or l == zeros:
		print('Bob')
	elif ones == 1 or zeros == 1:
		print('Alice')
	elif ones % 2 != 0 and zeros % 2 == 0 or (ones % 2 == 0 and zeros % 2 != 0):
		print('Alice')
	elif ones % 2 == 0 and zeros % 2 == 0 or (ones % 2 != 0 and zeros % 2 != 0):
		print('Bob')


try:
	t = int(input())
except:
	quit()
for _ in range(t):
	n = int(input())
	s = input()
	ones = s.count('1')
	zeros = s.count('0')
	if ones == n or zeros == n:
		print('Bob')
		continue
	if ones == 1 or zeros == 1:
		print('Alice')
		continue
	if n % 2 == 1:
		print('Alice')
	else:
		print('Bob')


from sys import stdin, stdout

def input():
	return stdin.readline().rstrip('\r\n')
for i in range(int(input())):
	n = int(input())
	t = input().count('0')
	if t == 0 or t == n:
		print('Bob')
		continue
	if t == 1 or t == n - 1 or n % 2:
		print('Alice')
		continue
	print('Bob')


for _ in range(int(input())):
	N = int(input())
	st = str(input())
	(ct, ct1) = (0, 0)
	for i in range(0, N):
		if st[i] == '0':
			ct += 1
		else:
			ct1 += 1
	if min(ct, ct1) == 0:
		print('Bob')
	elif min(ct, ct1) == 1:
		print('Alice')
	elif N % 2 == 0:
		print('Bob')
	else:
		print('Alice')


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			print(p)
for _ in range(int(input())):
	n = int(input())
	s = input()
	one = s.count('1')
	zero = s.count('0')
	if one == 0 or zero == 0:
		print('Bob')
	elif one == 1 or zero == 1:
		print('Alice')
	elif n % 2 == 1:
		print('Alice')
	else:
		print('Bob')


def check(n, s):
	one = s.count('1')
	zero = s.count('0')
	if n == one or n == zero:
		return 'Bob'
	if one == 1 or zero == 1:
		return 'Alice'
	if n % 2 == 0:
		return 'Bob'
	else:
		return 'Alice'
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(check(n, s))


import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)

def solve():
	n = int(input())
	s = str(input())
	one = s.count('1')
	zero = s.count('0')
	if min(zero, one) == 0:
		print('Bob')
	elif min(zero, one) == 1:
		print('Alice')
	elif n % 2:
		print('Alice')
	else:
		print('Bob')
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	a = s.count('1')
	b = n - a
	if a == 0 or b == 0:
		print('Bob')
		continue
	if a == 1 or b == 1:
		print('Alice')
		continue
	c = max(a, b) - min(a, b)
	if c % 2 == 0:
		print('Bob')
	else:
		print('Alice')


try:
	for t in range(int(input())):
		N = int(input())
		S = str(input())
		count1 = 0
		count0 = 0
		for i in range(N):
			if S[i] == '1':
				count1 += 1
			else:
				count0 += 1
		if count1 == 0 or count0 == 0:
			print('Bob')
			continue
		elif count0 == 1 or count1 == 1:
			print('Alice')
			continue
		elif N % 2 == 0:
			print('Bob')
		else:
			print('Alice')
except:
	pass


import sys

def solve(counts_of_0s, counts_of_1s, N):
	if counts_of_1s == 0 or counts_of_0s == 0:
		print('Bob')
		return
	if counts_of_1s == 1 or counts_of_0s == 1:
		print('Alice')
		return
	if N % 2:
		print('Alice')
	else:
		print('Bob')

def main():
	test_case = int(sys.stdin.readline())
	for tc in range(test_case):
		N = int(sys.stdin.readline())
		string = str(sys.stdin.readline())
		(counts_of_1s, counts_of_0s) = (0, 0)
		for i in range(N):
			if string[i] == '1':
				counts_of_1s += 1
			else:
				counts_of_0s += 1
		solve(counts_of_0s, counts_of_1s, N)
main()


for _ in range(int(input())):
	n = int(input())
	s = input()
	z = 0
	o = 0
	for i in s:
		if i == '0':
			z += 1
		else:
			o += 1
	if z == 0 or o == 0:
		print('Bob')
	elif z == 1 or o == 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ones = s.count('1')
	zeros = s.count('0')
	if min(zeros, ones) == 0:
		print('Bob')
	elif min(zeros, ones) == 1:
		print('Alice')
	elif n % 2 == 1:
		print('Alice')
	else:
		print('Bob')


t = int(input())
while t:
	n = int(input())
	s = input().rstrip()
	(c1, c0) = (0, 0)
	for i in s:
		if i == '0':
			c0 += 1
		else:
			c1 += 1
	if c1 == 0 or c0 == 0:
		print('Bob')
	elif c1 == 1 or c0 == 1:
		print('Alice')
	elif n % 2 == 0:
		print('Bob')
	else:
		print('Alice')
	t -= 1


def mgc(n, a):
	(zero, one) = (0, 0)
	for i in a:
		if i == '1':
			one += 1
		else:
			zero += 1
	if min(zero, one) == 0:
		return 'Bob'
	elif min(zero, one) == 1:
		return 'Alice'
	else:
		if n % 2:
			return 'Alice'
		return 'Bob'
for _ in range(int(input())):
	n = int(input())
	arr = input()
	print(mgc(n, arr))


def f(s, n):
	zcount = s.count('0')
	ocount = s.count('1')
	(mnm, mxm) = (min(zcount, ocount), max(zcount, ocount))
	if mnm == 0:
		return 'Bob'
	if mnm == 1:
		return 'Alice'
	count = (n - 4) % 2
	if count == 0:
		return 'Bob'
	return 'Alice'
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(f(s, n))


def solve():
	n = int(input())
	s = input()
	if min(s.count('0'), s.count('1')) == 0:
		print('Bob')
		return
	if min(s.count('0'), s.count('1')) == 1:
		print('Alice')
		return
	if n % 2 != 0:
		print('Alice')
	else:
		print('Bob')
t = int(input())
while t != 0:
	solve()
	t -= 1


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	(o, z) = (0, 0)
	for i in s:
		if i == '1':
			o += 1
		else:
			z += 1
	if min(o, z) == 0:
		print('Bob')
	elif min(o, z) == 1:
		print('Alice')
	elif n % 2:
		print('Alice')
	else:
		print('Bob')


for i in range(int(input())):
	n = int(input())
	string = input()
	cnt_zero = string.count('0')
	cnt_one = string.count('1')
	maxim = max(cnt_one, cnt_zero)
	minim = min(cnt_one, cnt_zero)
	if minim == 1:
		print('Alice')
	elif minim == 0:
		print('Bob')
	elif minim % 2 == 0 and maxim % 2 != 0:
		print('Alice')
	elif minim % 2 == 0 and maxim % 2 == 0:
		print('Bob')
	elif minim % 2 != 0 and maxim % 2 == 0:
		print('Alice')
	else:
		print('Bob')


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	x = s.count('0')
	y = s.count('1')
	if x == 0 or y == 0:
		print('Bob')
	elif x == 1 or y == 1:
		print('Alice')
	elif n % 2 == 1:
		print('Alice')
	else:
		print('Bob')


for _ in range(int(input())):
	n = int(input())
	s = input()
	x = 0
	y = 0
	for i in range(n):
		if s[i] == '0':
			x += 1
		else:
			y += 1
	if x == 0:
		print('Bob')
	elif y == 0:
		print('Bob')
	elif x != y and (x == 1 or y == 1):
		print('Alice')
	elif x == y != 1:
		print('Bob')
	elif x == y == 1:
		print('Alice')
	else:
		if x > y:
			a = x - y
		else:
			a = y - x
		if a % 2 == 0:
			print('Bob')
		else:
			print('Alice')


def main():
	n = int(input())
	s = input()
	one = 0
	zero = 0
	for x in s:
		if x == '0':
			zero += 1
		else:
			one += 1
	if one == 0 or zero == 0:
		return 'Bob'
	if one == 1 or zero == 1:
		return 'Alice'
	if n % 2 == 1:
		return 'Alice'
	else:
		return 'Bob'
for _ in range(int(input())):
	print(main())