← 返回题目列表

Codeforces · 2004/E

E. 不是 Nim 问题

中文机器翻译题面 查看原题

两个玩家,Alice 和 Bob,正在玩游戏。他们有 $$$n$$$ 堆石头,第 $$$i$$$ 堆最初包含 $$$a_i$$$ 石头。

在自己的回合中,玩家可以选择任意一堆石子并从中取出任意正数的石子,但有一个条件:

- 令堆中当前石头的数量为$$$x$$$。不允许从堆中取出一些石头$$$y$$$,使得$$$x$$$ 和$$$y$$$ 的最大公约数不等于$$$1$$$。

无法移动的玩家失败。两个玩家都发挥最佳(也就是说,如果一个玩家有一个可以让他们获胜的策略,无论对手如何反应,他们都会获胜)。爱丽丝先走。

确定谁会获胜。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成:

- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,如果 Alice 获胜则输出 Alice,如果 Bob 获胜则输出 Bob。

示例

输入 #1

3
3
3 2 9
4
3 3 6 1
5
1 2 3 4 5

输出 #1

Bob
Alice
Bob