CF1728D.Letter Picking

Alice and Bob are playing a game. Initially, they are given a non-empty string $s$, consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty.

Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string $s$, removes it from $s$ and prepends (adds to the beginning) it to their own string.

The game ends when the string $s$ becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw.

A string $a$ is lexicographically smaller than a string $b$ if there exists such position $i$ that $a_j = b_j$ for all $j \lt i$ and $a_i \lt b_i$.

What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?

爱丽丝和鲍勃正在玩一个游戏。初始时，他们得到一个非空字符串 $s$，该字符串仅由小写拉丁字母组成，且其长度为偶数。每位玩家各自还拥有一个属于自己的字符串，初始为空。

爱丽丝先手，之后双方轮流进行操作。在一次操作中，当前玩家从字符串 $s$ 的首端或尾端取走一个字母，将其从 $s$ 中删除，并将其添加到自己字符串的开头（即前置）。

当字符串 $s$ 变为空时，游戏结束。字符串字典序更小的一方获胜；若双方字符串相等，则为平局。

字符串 $a$ 字典序小于字符串 $b$，当且仅当存在某个位置 $i$，使得对所有 $j \lt i$ 都有 $a_j = b_j$，且 $a_i \lt b_i$。

若双方均以最优策略进行游戏（即：均优先争取胜利；若无法获胜，则争取平局），则游戏结果如何？

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

Each testcase consists of a single line — a non-empty string $s$, consisting of lowercase Latin letters. The length of the string $s$ is even.

The total length of the strings over all testcases doesn't exceed $2000$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。

每个测试用例由一行组成——一个非空字符串 $s$，仅由小写拉丁字母构成。字符串 $s$ 的长度为偶数。

所有测试用例中字符串的总长度不超过 $2000$。

For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".

对于每个测试用例，如果双方都采取最优策略，请输出游戏的结果。若 Alice 获胜，输出 “Alice”；若 Bob 获胜，输出 “Bob”；若为平局，输出 “Draw”。

One of the possible games Alice and Bob can play in the first testcase:

1. Alice picks the first letter in $s$: $s=$"orces", $a=$"f", $b=$"";
2. Bob picks the last letter in $s$: $s=$"orce", $a=$"f", $b=$"s";
3. Alice picks the last letter in $s$: $s=$"orc", $a=$"ef", $b=$"s";
4. Bob picks the first letter in $s$: $s=$"rc", $a=$"ef", $b=$"os";
5. Alice picks the last letter in $s$: $s=$"r", $a=$"cef", $b=$"os";
6. Bob picks the remaining letter in $s$: $s=$"", $a=$"cef", $b=$"ros".

Alice wins because "cef" < "ros". Neither of the players follows any strategy in this particular example game, so it doesn't show that Alice wins if both play optimally.

第一个测试用例中 Alice 和 Bob 可能进行的一场游戏如下：

1. Alice 选取 $s$ 中的第一个字母：$s=$"orces"，$a=$"f"，$b=$""；
2. Bob 选取 $s$ 中的最后一个字母：$s=$"orce"，$a=$"f"，$b=$"s"；
3. Alice 选取 $s$ 中的最后一个字母：$s=$"orc"，$a=$"ef"，$b=$"s"；
4. Bob 选取 $s$ 中的第一个字母：$s=$"rc"，$a=$"ef"，$b=$"os"；
5. Alice 选取 $s$ 中的最后一个字母：$s=$"r"，$a=$"cef"，$b=$"os"；
6. Bob 选取 $s$ 中剩余的唯一字母：$s=$""，$a=$"cef"，$b=$"ros"。

Alice 获胜，因为 "cef" < "ros"。在本示例游戏中，双方均未采用任何特定策略，因此该例子并不能说明当双方都采取最优策略时 Alice 必然获胜。