The only difference between the easy and hard versions is that the given string $s$ in the easy version is initially a palindrome, this condition is not always true for the hard version.

A palindrome is a string that reads the same left to right and right to left. For example, "101101" is a palindrome, while "0101" is not.

Alice and Bob are playing a game on a string $s$ (which is initially a palindrome in this version) of length $n$ consisting of the characters '0' and '1'. Both players take alternate turns with Alice going first.

In each turn, the player can perform one of the following operations:

Choose any $i$ ($1 \le i \le n$), where $s[i] =$ '0' and change $s[i]$ to '1'. Pay 1 dollar.

Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse. That is, if Alice reverses the string, then Bob can't reverse in the next move, and vice versa.

Reversing a string means reordering its letters from the last to the first. For example, "01001" becomes "10010" after reversing.

The game ends when every character of string becomes '1'. The player who spends minimum dollars till this point wins the game and it is a draw if both spend equal dollars. If both players play optimally, output whether Alice wins, Bob wins, or if it is a draw.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^3$). Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^3$).

The second line of each test case contains the string $s$ of length $n$, consisting of the characters '0' and '1'. It is guaranteed that the string $s$ is a palindrome and contains at least one '0'.

Note that there is no limit on the sum of $n$ over test cases.


-----Output-----

For each test case print a single word in a new line:

"ALICE", if Alice will win the game,

"BOB", if Bob will win the game,

"DRAW", if the game ends in a draw.


-----Examples-----

Input
2
4
1001
1
0
Output
BOB
BOB


-----Note-----

In the first test case of the example,

in the $1$-st move Alice has to perform the $1$-st operation, since the string is currently a palindrome.

in the $2$-nd move Bob reverses the string.

in the $3$-rd move Alice again has to perform the $1$-st operation. All characters of the string are '1', game over.

Alice spends $2$ dollars while Bob spends $0$ dollars. Hence, Bob always wins.

Difficulty: EASY
Tags: Game theory

Constructive algorithms

Starter code:

Solutions:
list_ans = []
for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('0')
	if n % 2 == 0:
		if a != 0:
			list_ans.append('BOB')
		else:
			list_ans.append('DRAW')
	elif a == 0:
		list_ans.append('DRAW')
	elif a > 1 and s[(n - 1) // 2] != '1':
		list_ans.append('ALICE')
	else:
		list_ans.append('BOB')
for item in list_ans:
	print(item)


import math

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

def stringlsit():
	return input().split(' ')

def solve():
	n = int(input())
	s = input()
	c = s.count('0')
	if c > 1 and n % 2 == 1 and (s[n // 2] == '0'):
		return 'ALICE'
	return 'BOB'
t = input()
for tt in range(int(t)):
	print(solve())


import math as m
for i in range(int(input())):
	a = int(input())
	b = input()
	c = b.count('0')
	if c == 1:
		print('BOB')
	elif c % 2 == 0:
		print('BOB')
	else:
		print('ALICE')


def solve(s):
	alice = 0
	bob = 0
	s = list(s)
	print(s)
	can_reverse = False
	last_index = None
	index_with_0 = []
	is_alice_turn = True
	for i in range(len(s) // 2 + 1):
		if s[i] == '0':
			index_with_0.append(i)
	if len(s) == 1:
		if s[0] == '1':
			print('DRAW')
		else:
			print('BOB')
		return
	while len(index_with_0) > 0:
		if can_reverse:
			s = s[::-1]
			can_reverse = False
		else:
			if is_alice_turn:
				alice += 1
			else:
				bob += 1
			if last_index == None:
				if len(s) % 2 != 0:
					if s[len(s) // 2] == '0':
						s[len(s) // 2] = '1'
						last_index = None
						can_reverse = True
				else:
					i = index_with_0.pop()
					last_index = i
					s[i] = '1'
					can_reverse = False
			else:
				s[last_index] = '1'
				last_index = None
				can_reverse = True
	if alice == bob:
		print('DRAW')
	elif alice > bob:
		print('BOB')
	else:
		print('ALICE')

def solve2(s):
	n = s.count('0')
	if n == 0:
		print('DRAW')
	elif n == 1:
		print('BOB')
	elif n % 2 == 0:
		print('BOB')
	else:
		print('ALICE')
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	solve2(s)


t = int(input())
for i in range(0, t):
	n = int(input())
	gameString = input()
	alice = 0
	bob = 0
	if n % 2 == 0 or n == 1:
		print('BOB')
	else:
		ones = gameString.count('1')
		midpoint = int(n / 2)
		if gameString[midpoint] == '0' and ones != n - 1:
			print('ALICE')
		else:
			print('BOB')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = s.count('0')
	if c == 1:
		print('BOB')
	elif c % 2 == 0:
		print('BOB')
	else:
		print('ALICE')


for _ in [0] * int(input()):
	n = int(input())
	x = input()
	yy = x.count('0')
	if n > 1 and n % 2 == 1 and (yy > 1) and (x[n // 2] == '0'):
		print('ALICE')
	elif yy == 0:
		print('DRAW')
	else:
		print('BOB')


for i in range(int(input())):
	n = int(input())
	s = input()
	if len(s) > 1:
		if (len(s) % 2 == 1) & (s[len(s) // 2] == '0'):
			if s.count('0') == 1:
				print('BOB')
			else:
				print('ALICE')
		else:
			print('BOB')
	else:
		print('BOB')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if '0' not in s:
		print('DRAW')
	elif n % 2:
		i = n // 2
		if s[i] == '1':
			print('BOB')
		elif s.count('0') == 1:
			print('BOB')
		else:
			print('ALICE')
	else:
		print('BOB')


for s in [*open(0)][2::2]:
	n = s.count('0')
	print('ABLOIBC E'[(n < 2) | (n & 1 < 1)::2])


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('0')
	if a == 1:
		print('BOB')
	elif a % 2:
		print('ALICE')
	else:
		print('BOB')


import sys
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) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	s = insr()
	if n == 1:
		if s[0] == '0':
			print('BOB')
		else:
			print('DRAW')
	elif n % 2 == 0 or s[n // 2] == '1':
		c = s[:n // 2].count('0')
		if c == 0:
			print('DRAW')
		else:
			print('BOB')
	else:
		c = s[:n // 2].count('0')
		if c == 0:
			print('BOB')
		else:
			print('ALICE')


for pratyush in range(int(input())):
	n = int(input())
	s = str(input())
	c = s.count('0')
	if c % 2 and c != 1:
		print('ALICE')
	else:
		print('BOB')


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = s.count('0')
	if cnt & 1 and cnt != 1:
		print('ALICE')
	else:
		print('BOB')


for t in range(int(input())):
	n = int(input())
	s = input()
	zero = s.count('0')
	if zero % 2 != 0 and zero > 2:
		print('ALICE')
	else:
		print('BOB')


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	s = stdin.readline().strip()
	cnt = s.count('0')
	if cnt % 2 == 0 or cnt == 1:
		print('BOB')
	else:
		print('ALICE')


n = int(input())
for i in range(n):
	x = int(input())
	s = input()
	if len(s) % 2 == 0 or len(s) == 1:
		print('BOB')
	else:
		cnt0 = s.count('0')
		s0 = (len(s) + 1) // 2
		if s[s0 - 1] == '0' and cnt0 > 1:
			print('ALICE')
		else:
			print('BOB')


for __ in range(int(input())):
	n = int(input())
	s = input()
	if n % 2 == 0:
		print('BOB')
	elif s[n // 2] == '0' and s.count('0') > 1:
		print('ALICE')
	else:
		print('BOB')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().rstrip()
	if s == '1' * n:
		print('DRAW')
	else:
		h = s.count('0')
		if h == 1:
			print('BOB')
		elif h % 2 == 0:
			print('BOB')
		else:
			print('ALICE')


t = int(input())
while t:
	n = int(input())
	s = input()
	if s.count('0') % 2 == 0:
		print('BOB')
	elif s.count('0') == 1:
		print('BOB')
	else:
		print('ALICE')
	t -= 1


t = int(input())
result = []
for i in range(t):
	n = int(input())
	s = input()
	if (n % 2 == 1) & (s.count('0') > 1):
		if s[n // 2] == '0':
			result.append('ALICE')
		else:
			result.append('BOB')
	elif n * '1' == s:
		result.append('DRAW')
	else:
		result.append('BOB')
for i in result:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	if n % 2 == 0 or s[n // 2] == '1' or s.count('0') == 1:
		print('BOB')
	else:
		print('ALICE')


import math
for t in range(int(input())):
	n = int(input())
	a = input()
	c = a.count('0')
	if c == 1 or c % 2 == 0:
		print('BOB')
	else:
		print('ALICE')


import math
modulo = 10 ** 9 + 7
n_tests = int(input())
for test in range(n_tests):
	lens = int(input())
	pal = input()
	nul = pal.count('0')
	if nul == 1:
		print('BOB')
	elif nul % 2 == 0:
		print('BOB')
	else:
		print('ALICE')


def solve():
	N = int(input())
	S = input()
	cnt0 = S.count('0')
	if cnt0 == 0:
		return 'DRAW'
	elif cnt0 == 1:
		return 'BOB'
	elif cnt0 % 2 == 1:
		return 'ALICE'
	else:
		return 'BOB'
T = int(input())
for i in range(T):
	print(solve())


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	zeroes = s.count('0')
	if zeroes == 1:
		print('BOB')
	elif zeroes == 0:
		print('DRAW')
	elif zeroes % 2 == 0:
		print('BOB')
	else:
		print('ALICE')


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = s.count('0')
	if l == 0:
		print('DRAW')
	elif n % 2 == 1 and s[n // 2] == '0':
		if l == 1:
			print('BOB')
		elif l == 2:
			print('DRAW')
		else:
			print('ALICE')
	else:
		print('BOB')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	c0 = s.count('0')
	if c0 == 0:
		print('DRAW')
	elif c0 % 2 == 0 or c0 == 1:
		print('BOB')
	else:
		print('ALICE')


for _ in range(int(input())):
	n = int(input())
	s = input()
	z = s.count('0')
	if z == 1 or z % 2 == 0:
		print('BOB')
	elif z >= 3 and z % 2 == 1:
		print('ALICE')


for _ in range(int(input())):
	n = int(input())
	l = input()
	c = l.count('0')
	if c == 0:
		print('DRAW')
	if c == 1 or c % 2 == 0:
		print('BOB')
	else:
		print('ALICE')


from math import log
from math import floor
t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	l = st.count('0')
	if l == 1:
		print('BOB')
	elif l % 2:
		print('ALICE')
	else:
		print('BOB')


def solve(s):
	bob = 0
	alice = 1
	cnt = 0
	zeros = s.count('0')
	if zeros == 0:
		print('DRAW')
		return
	elif zeros == 1:
		print('BOB')
		return
	if s[(len(s) - 1) // 2] == '0' and len(s) % 2 == 1:
		print('ALICE')
	else:
		print('BOB')
for _ in range(int(input())):
	n = int(input())
	solve(input())


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ones = s.count('1')
	zeroes = s.count('0')
	if n == ones:
		print('DRAW')
	elif n % 2 == 0:
		print('BOB')
	elif n == 1:
		print('BOB')
	elif s[n // 2] == '0' and zeroes > 1:
		print('ALICE')
	else:
		print('BOB')


import sys
if not sys.warnoptions:
	import warnings
	warnings.simplefilter('ignore')

def ii():
	return int(input())

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

def ls():
	return [i for i in input().split()]
for i in range(int(input())):
	n = ii()
	s = input()
	zeros = s.count('0')
	if n % 2 == 0:
		print('BOB')
	elif s[n // 2] == '0':
		zeros -= 1
		if zeros == 0:
			print('BOB')
		else:
			print('ALICE')
	else:
		print('BOB')


try:

	def solve():
		n = int(input())
		string = input()
		count = string.count('0')
		if count == 0:
			print('DRAW')
		elif count == 1:
			print('BOB')
		elif count & 1:
			print('ALICE')
		else:
			print('BOB')
	test = int(input())
	count = 1
	while count <= test:
		solve()
		count += 1
except EOFError:
	print(' ')


for _ in range(int(input())):
	n = int(input())
	s = input()
	z = s.count('0')
	z //= 2
	c = 0
	if n & 1:
		c = s[n // 2] == '0'
	if c == 0:
		if z == 0:
			print('DRAW')
		else:
			print('BOB')
	elif z == 0:
		print('BOB')
	else:
		print('ALICE')


def main():
	n = int(input())
	for _ in range(n):
		int(input())
		s = input()
		if len(s) % 2 != 0 and s[len(s) // 2] == '0' and (s.count('0') >= 3):
			print('ALICE')
		else:
			print('BOB')
main()


for _ in range(int(input())):
	n = int(input())
	s = input()
	if all(map(int, s)):
		print('DRAW')
	elif n & 1 == 0:
		print('BOB')
	elif s[n // 2] == '0':
		if s.count('0') == 1:
			print('BOB')
		else:
			print('ALICE')
	else:
		print('BOB')


n = int(input())
L = []
for i in range(n):
	k = int(input())
	l = input()
	isZero = True
	isOdd = False
	if k % 2 == 0:
		m = int(k / 2)
	else:
		m = int((k - 1) / 2)
		if l[m] == '0':
			isOdd = True
	for j in range(m):
		if l[j] == '0':
			isZero = False
			break
	if isZero:
		if isOdd:
			L.append('BOB')
		else:
			L.append('DRAW')
	elif isOdd:
		L.append('ALICE')
	else:
		L.append('BOB')
for i in L:
	print(i)


from sys import stdin as sin

def aint():
	return int(input())

def amap():
	return map(int, sin.readline().split())

def alist():
	return list(map(int, sin.readline().split()))

def astr():
	return input()
from math import log
for i in range(aint()):
	n = aint()
	s = input()
	o = s.count('0')
	if o == 0:
		print('DRAW')
	elif o % 2 == 0:
		print('BOB')
	elif o == 1:
		print('BOB')
	else:
		print('ALICE')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	alice = 0
	bob = 0
	a = s.count('1')
	b = s.count('0')
	if s.count('1') == len(s):
		print('DRAW')
	elif b % 2 == 0 or b == 1:
		print('BOB')
	else:
		print('ALICE')


T = int(input())
for _ in range(T):
	N = int(input())
	S = input().rstrip()
	zeros = S.count('0')
	if zeros % 2 == 0:
		print('BOB')
	elif zeros == 1:
		print('BOB')
	else:
		print('ALICE')


t = int(input())
while t:
	n = int(input())
	s = input()
	c = False
	if n % 2 == 1 and s[n // 2] == '0':
		for i in s[:n // 2]:
			if i == '0':
				c = True
				break
		if c == False:
			print('BOB')
		else:
			print('ALICE')
	else:
		print('BOB')
	t -= 1


import sys
import math

def scan(input_type='int'):
	return list(map(int, sys.stdin.readline().strip().split()))

def solution():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		z = s.count('0')
		if z == 0:
			print('DRAW')
		elif z % 2 == 0:
			print('BOB')
		elif z == 1:
			print('BOB')
		else:
			print('ALICE')
solution()


cases = int(input())
for case in range(0, cases):
	n = int(input())
	s = input()
	h = '1' * n
	if n % 2 == 0 or len(s) == 1:
		print('BOB')
		continue
	if n % 2 != 0 and s[int((n - 1) / 2)] == '0':
		if all((s[i] == '1' for i in range(0, int((n - 1) / 2)))):
			print('BOB')
		else:
			print('ALICE')
		continue
	print('BOB')


cases = int(input())
for _ in range(cases):
	num = int(input())
	s = input()
	zero = s.count('0')
	if zero % 2 == 0 or zero == 1:
		print('BOB')
	else:
		print('ALICE')


for _ in range(int(input())):
	n = int(input())
	s = input()
	zero = s.count('0')
	if n & 1:
		if n == 1:
			if s[0] == '1':
				print('DRAW')
			else:
				print('BOB')
		elif s[n >> 1] == '0':
			if zero == 1:
				print('BOB')
			else:
				print('ALICE')
		else:
			print('BOB')
	elif zero:
		print('BOB')
	else:
		print('DRAW')


for tc in range(int(input())):
	l = int(input())
	s = input()
	(A, B) = (0, 0)
	c = {}
	c['A'] = 0
	c['B'] = 0
	n = s.count('0')
	if n == 1:
		print('BOB')
		continue
	if n % 2 != 0:
		print('ALICE')
	else:
		print('BOB')


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	ls = list(s)
	zeros = ls.count('0')
	ones = n - zeros
	if n % 2 == 1:
		if zeros % 2 == 1 and zeros > 1:
			print('ALICE')
		else:
			print('BOB')
	elif zeros == 0:
		print('DRAW')
	else:
		print('BOB')


import math
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	a = s.count('0')
	b = a // 2
	if a == 1:
		print('BOB')
	elif n % 2 == 0:
		print('BOB')
	else:
		k = n // 2
		if s[k] == '0':
			print('ALICE')
		else:
			print('BOB')


for i in range(int(input())):
	n = int(input())
	s = str(input())
	n0 = s.count('0')
	if n0 == 0:
		print('DRAW')
	elif n0 == 1 or n % 2 == 0:
		print('BOB')
	elif s[int((n - 1) / 2)] == '0':
		print('ALICE')
	else:
		print('BOB')


import math
for _ in range(int(input())):
	n = int(input())
	inp = input()
	c = inp.count('0')
	if c == 1:
		print('BOB')
		continue
	if c == 0:
		print('DRAW')
		continue
	if c % 2 == 0:
		print('BOB')
		continue
	if c % 2 == 1:
		print('ALICE')


def solve():
	n = int(input())
	nums = len(str(input()).replace('1', ''))
	if nums == 1:
		print('BOB')
	elif nums % 2 == 1:
		print('ALICE')
	else:
		print('BOB')

def main():
	for _ in range(int(input())):
		solve()
main()


for _ in range(int(input())):
	k = int(input())
	n = input()
	if n.count('0') == 1 or n.count('0') % 2 == 0:
		print('BOB')
	else:
		print('ALICE')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	is_pal = s == s[::-1]
	if s == '0' or s.count('0') == 1:
		print('BOB')
	elif not is_pal or (is_pal and len(s) % 2 == 1 and (s[len(s) // 2] == '0')):
		print('ALICE')
	else:
		print('BOB')


t = int(input())
while t:
	num = int(input())
	str = input()
	zero = str.count('0')
	if zero == 1 or zero % 2 == 0:
		print('BOB')
	else:
		print('ALICE')
	t -= 1


n = int(input())
for i in range(n):
	t = int(input())
	s = input()
	num = s.count('0')
	if num == 0:
		print('DRAW')
	elif t % 2 == 0 or num % 2 == 0 or num == 1:
		print('BOB')
	else:
		print('ALICE')


import math

def solve():
	n = int(input())
	s = input()
	z = s.count('0')
	if z % 2 == 1 and z != 1:
		print('ALICE')
	else:
		print('BOB')
t = int(input())
while t > 0:
	t -= 1
	solve()


for u in range(int(input())):
	n = int(input())
	s = input()
	x = s.count('0')
	if s == '1' * n:
		print('DRAW')
	elif s == '0':
		print('BOB')
	elif x % 2 and x != 1:
		print('ALICE')
	else:
		print('BOB')


t = int(input())
for i in range(t):
	k = int(input())
	a = input()
	z = a.count('0')
	if z == 0:
		print('DRAW')
	elif z == 1 or z % 2 == 0:
		print('BOB')
	else:
		print('ALICE')


def isPalindrome(s):
	return s == s[::-1]
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	counter = s.count('0')
	if counter == 1:
		print('BOB')
	elif counter % 2 == 0:
		print('BOB')
	else:
		print('ALICE')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	x = s.count('0')
	if x == 0:
		print('DRAW')
	elif x == 1:
		print('BOB')
	elif x % 2 == 0:
		print('BOB')
	elif x % 2 != 0:
		print('ALICE')


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	c = s.count('0')
	if c & 1:
		if c == 1:
			print('BOB')
		else:
			print('ALICE')
	elif c == 0:
		print('ALICE')
	else:
		print('BOB')


t = int(input())
for i in range(t):
	n = int(input())
	m = input()
	ocount = m.count('0')
	if ocount % 2 != 0:
		if ocount == 1:
			print('BOB')
		else:
			print('ALICE')
	else:
		print('BOB')


t = int(input())
for i in range(0, t):
	n = int(input())
	k = input()
	if len(k) == 1 and k[0] == '0':
		print('BOB')
	elif len(k) == 1 and k[0] == '1':
		print('DRAW')
	elif k.count('0') == 0:
		print('DRAW')
	elif len(k) % 2 == 0:
		print('BOB')
	else:
		j = len(k) // 2
		if k[j] == '1':
			print('BOB')
		elif k[j] == '0' and k.count('0') == 1:
			print('BOB')
		else:
			print('ALICE')