D. Выбор букв
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. Изначально им дана непустая строка $$$s$$$, состоящая из строчных латинских букв. Длина строки четная. У каждого игрока также есть своя строка, изначально пустая.

Алиса начинает, затем они ходят по очереди. За один ход игрок берет либо первую, либо последнюю букву из строки $$$s$$$, удаляет ее из $$$s$$$ и приписывает ее в начало своей строки.

Игра заканчивается, когда строка $$$s$$$ становится пустой. Побеждает игрок, у которого строка лексикографически меньше. Если строки у игроков одинаковые, то это ничья.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если существует такая позиция $$$i$$$, что $$$a_j = b_j$$$ для всех $$$j < i$$$ и $$$a_i < b_i$$$.

С каким результатом закончится игра, если оба игрока играют оптимально (т. е. оба игрока стараются выиграть; если они не могут, то стараются сыграть вничью)?

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из одной строки — непустой строки $$$s$$$, состоящей из строчных латинских букв. Длина строки $$$s$$$ четная.

Суммарная длина строк по всем наборам входных данных не превосходит $$$2000$$$.

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

На каждый набор входных данных выведите результат игры, если оба игрока играют оптимально. Если Алиса выиграет, то выведите «Alice». Если Боб выиграет, то выведите «Bob». Если игра закончится вничью, то выведите «Draw».

Пример
Входные данные
2
forces
abba
Выходные данные
Alice
Draw
Примечание

Одна из возможных игр, которую могут сыграть Алиса и Боб в первом наборе входных данных:

  1. Алиса выбирает первую букву в $$$s$$$: $$$s=$$$«orces», $$$a=$$$«f», $$$b=$$$«»;
  2. Боб выбирает последнюю букву в $$$s$$$: $$$s=$$$«orce», $$$a=$$$«f», $$$b=$$$«s»;
  3. Алиса выбирает последнюю букву в $$$s$$$: $$$s=$$$«orc», $$$a=$$$«ef», $$$b=$$$«s»;
  4. Боб выбирает первую букву в $$$s$$$: $$$s=$$$«rc», $$$a=$$$«ef», $$$b=$$$«os»;
  5. Алиса выбирает последнюю букву в $$$s$$$: $$$s=$$$«r», $$$a=$$$«cef», $$$b=$$$«os»;
  6. Боб выбирает оставшуюся букву в $$$s$$$: $$$s=$$$«», $$$a=$$$«cef», $$$b=$$$«ros».

Алиса выигрывает, потому что «cef» < «ros». Ни один из игроков не следует никакой стратегии в конкретно этой игре, поэтому она не показывает, что Алиса выигрывает, если игроки играют оптимально.