← 返回题目列表

Codeforces · 2200/E

E. 分裂之战

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

Alice 和 Bob 正在数组 $$$a$$$ 上玩游戏,最初包含 $$$n$$$ 正整数,Alice 先玩。

在每个玩家的回合中,如果$$$a$$$非递减$$$^{\text{*}}$$$,则游戏立即结束。否则,玩家可以从数组中选择一个元素 $$$x$$$ 和正整数 $$$1 \lt y,z \lt x$$$ 使得 $$$x=yz$$$ 并将数组中的 $$$x$$$ 替换为两个元素 $$$y$$$ 和 $$$z$$$(在 $$$x$$$ 的原始位置以任意顺序)。如果不可能进行这样的移动,则游戏结束。

游戏结束后,如果 $$$a$$$ 不减,则 Bob 获胜。否则,爱丽丝获胜。如果双方都发挥最佳,确定谁将赢得比赛。

$$$^{\text{*}}$$$$$$a$$$ 是非递减的,如果 $$$a_i\leq a_{i+1}$$$ 对于所有 $$$1\leq i\leq m-1$$$ 是非递减的,其中 $$$m$$$ 是 $$$a$$$ 的长度。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果 Alice 获胜,则输出包含“Alice”的行,如果 Bob 获胜,则输出包含“Bob”的行。 分级机区分大小写。

示例

输入
复制

4
10
10 9 8 7 6 5 4 3 2 1
3
1 8192 677
2
6 5
2
6 7

输出
复制

Alice
Bob
Alice
Bob

注意

在第一个测试用例中,如果两个玩家都发挥最佳,Alice 将获胜。

在第二个测试用例中,无论 Alice 采取什么行动,Bob 总能获胜。

在第三个测试用例中,Alice 可以通过将 $$$6$$$ 替换为 $$$3$$$ 和 $$$2$$$ 来获胜。

在第四个测试用例中,游戏立即结束,Bob 获胜。