Alice 和 Bob 正在玩游戏。最初,它们被赋予一个非空字符串 $$$s$$$,由小写拉丁字母组成。绳子的长度是偶数。每个玩家也有自己的字符串,最初是空的。
爱丽丝开始,然后他们交替移动。在一次移动中,玩家取出字符串 $$$s$$$ 的第一个或最后一个字母,将其从 $$$s$$$ 中删除,并将其添加到自己的字符串前面(添加到开头)。
当字符串 $$$s$$$ 变空时游戏结束。获胜者是具有按字典顺序排列的较小字符串的玩家。如果玩家的绳子相等,则平局。
如果对于所有 $$$j < i$$$ 和 $$$a_i < b_i$$$,存在 $$$i$$$ 位置 $$$a_j = b_j$$$,则字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$。
如果两个玩家都发挥最佳状态(例如,两个玩家都试图获胜;如果不能,则尝试平局),游戏结果是什么?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例都由一行组成 - 一个非空字符串 $$$s$$$,由小写拉丁字母组成。字符串 $$$s$$$ 的长度是偶数。
所有测试用例的字符串总长度不超过 $$$2000$$$。
输出
对于每个测试用例,如果两个玩家都发挥最佳,则打印游戏结果。如果 Alice 获胜,则打印“Alice”。如果鲍勃获胜,则打印“鲍勃”。如果是平局,则打印“平局”。
示例
输入 #1
2 forces abba
输出 #1
Alice Draw
注意
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”。在这个特定的示例游戏中,两个玩家都没有遵循任何策略,因此并不表明如果双方都发挥最佳状态,爱丽丝就会获胜。