B2. Игра на палиндроме (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между простой и сложной версией заключается в том, что $$$s$$$ в простой версии изначально палиндром, что не всегда верно в сложной версии.

Палиндромом называется строка, читающаяся одинаково слева направо и справа налево. Например, «101101» — палиндром, а «0101» — нет.

Алиса и Боб играют в игру со строкой $$$s$$$ длины $$$n$$$ состоящей из символов '0' и '1'. Оба игрока ходят по очереди, и Алиса делает первый ход.

Каждый ход игрок может сделать одну из следующих операций:

  1. Выбрать любое $$$i$$$ ($$$1 \le i \le n$$$) такое, что$$$s[i] =$$$ '0' и заменить $$$s[i]$$$ на '1'. Цена такого ходя 1 доллар.
  2. Развернуть всю строку, заплатив 0 долларов. Эта операция доступна только в том случае, если сейчас строка НЕ палиндром, и последняя операция была не разворотом. Это значит, что если Алиса развернула строк, тогда Боб не может развернуть ее следующим ходом, и наоборот.

Под разворотом строки подразумевается переупорядочивание символов от последнего к первому. Например, «01001» после разворота становится «10010».

Игра заканчивается тогда, когда вся строка состоит из '1'. Игрок, потратившей меньше долларов, побеждает. Если оба игрока потратили одинаковую сумму, то игра завершается ничьей. Выведите результат игры, если оба игрока действуют оптимально.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^3$$$). Далее следуют $$$t$$$ наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^3$$$).

Вторая строка набора содержит строку $$$s$$$ длины $$$n$$$, состоящую только из '0' и '1'. Гарантируется, что строка $$$s$$$ содержит минимум один '0'.

Обратите внимание, что ограничения на сумму $$$n$$$ по всем наборам входных данных нет.

Выходные данные

Для каждого набора входных данных выведите ответ:

  • «ALICE», если Алиса побеждает,
  • «BOB», если Боб побеждает,
  • «DRAW», если игра закончится ничьей.
Пример
Входные данные
3
3
110
2
00
4
1010
Выходные данные
ALICE
BOB
ALICE
Примечание

В первом примере,

  • на $$$1$$$-м ходу, Алиса использует $$$2$$$-ю операцию, чтобы развернуть строку, так как если она сделает $$$1$$$-ю операцию, то обязательно проиграет. Это заставляет Боба использовать $$$1$$$-ю операцию.
  • на $$$2$$$-м ходу Боб использует $$$1$$$-ю операцию, так как $$$2$$$-я не может быть использована два раза подряд. Все символы строки '1', игра окончена.
Алиса потратила $$$0$$$ долларов, а Боб $$$1$$$. Таким образом, Алиса победила.

Во втором примере,

  • на $$$1$$$-м ходу Алиса использует $$$1$$$-ю операцию, так как строка — палиндром.
  • на $$$2$$$-м ходу Боб разворачивает строку.
  • на $$$3$$$-м ходу Алиса должна использовать $$$1$$$-ю операцию. Все символы строки '1', игра окончена.
Алиса потратила $$$2$$$ доллара, а Боб $$$0$$$. Таким образом, Боб победил.