两个玩家,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