Nim 的经典游戏如下。有 $$$n$$$ 堆石头,$$$i$$$ 堆最初由 $$$a_i$$$ 石头组成。爱丽丝和鲍勃轮流;爱丽丝先走。轮到玩家时,玩家选择任意非空堆并从中移走任意正数的石子。拿走最后一块石头的玩家获胜。
在玩了很多 Nim 之后,Alice 和 Bob 决定稍微改变一下规则。在这个变体中,轮到的玩家不会选择一堆 - 他们的对手 为他们做这件事!然而,玩家仍然可以决定从该堆中移除石子的数量。
爱丽丝仍然先动。轮到爱丽丝时,鲍勃选择任意一个非空堆,然后爱丽丝从中取出任意正数的石子。类似地,轮到鲍勃时,爱丽丝选择任意一个非空堆,然后鲍勃从中取出任意正数的石子。
对于给定的堆中石子配置,确定如果两个玩家都遵循最优策略谁将获胜。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$,表示堆的数量 ($$$1 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$,表示堆中石子的数量 ($$$1 \le a_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果两个玩家都遵循最优策略,则打印游戏获胜者的名字:“爱丽丝“或”鲍勃".
示例
输入复制
331 2 311510 3 4 7 4
输出复制
BobAliceAlice
注意
在第一个测试用例中,游戏进行的一种可能的方式是:
- Bob 选择第一堆。爱丽丝从中取出 $$$1$$$ 石头。
- Alice 选择了第三堆。鲍勃从中取出了 $$$2$$$ 石头。
- 鲍勃选择了第三堆。爱丽丝从中取出 $$$1$$$ 石头。
- Alice 选择第二堆。鲍勃从中取出 $$$2$$$ 石头并获胜。
在第二个测试用例中,鲍勃选择了唯一的一堆石头,爱丽丝通过从中取出唯一的石头而获胜。