Alice 和 Bob 正在玩 $$$n$$$ 堆石子的游戏,其中第 $$$i$$$ 堆有 $$$a_i$$$ 石子。玩家轮流行动,爱丽丝先行动。
在每一步中,玩家都会执行以下三步过程:
1. 选择一个整数 $$$k$$$ ($$$1 \leq k \leq \frac n 2$$$)。请注意,对于不同的移动,$$$k$$$ 的值可能不同。
2. 移走 $$$k$$$ 堆石头。
3. 选择另外 $$$k$$$ 堆石头,并将每堆石头分成两堆。每堆新石子的数量必须是质数。
无法采取行动的玩家失败。
如果两名玩家都发挥最佳,确定谁会获胜。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 石子堆的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — 堆中石子的数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果 Alice 获胜,则输出“Alice”(不带引号),否则输出“Bob”(不带引号)。
您可以以任何大小写(大写或小写)输出每个字母。例如,字符串“alIcE”、“Alice”和“alice”都将被视为相同。
示例
输入 #1
4 2 2 1 3 3 5 7 4 4 6 8 10 5 8 8 8 8 8
输出 #1
Bob Alice Alice Bob
注意
在第一个测试用例中,有 $$$2$$$ 堆石头,分别有 $$$2$$$ 和 $$$1$$$ 石头。由于 $$$1$$$ 和 $$$2$$$ 都不能分割成两个素数,所以 Alice 无法移动,所以 Bob 获胜。
在第二个测试用例中,有 $$$3$$$ 堆石头,分别有 $$$3$$$、$$$5$$$ 和 $$$7$$$ 石头。 Alice可以选择$$$k = 1$$$,移走$$$7$$$石头堆,然后将$$$5$$$石头堆分成两堆素数石头,$$$2$$$和$$$3$$$。然后,这堆石头由 $$$3$$$ 石头堆组成,分别是 $$$3$$$、$$$2$$$ 和 $$$3$$$ 石头,让鲍勃没有有效的移动,所以爱丽丝获胜。
在第三个测试用例中,有 $$$4$$$ 堆石头,分别有 $$$4$$$、$$$6$$$、$$$8$$$ 和 $$$10$$$ 石头。 Alice 可以选择 $$$k = 2$$$,移除两堆 $$$8$$$ 和 $$$10$$$ 石头。她将 $$$4$$$ 石头堆分成两堆素数石头 $$$2$$$ 和 $$$2$$$,并将 $$$6$$$ 石头堆分成 $$$3$$$ 和 $$$3$$$ 石头两堆。然后,鲍勃没有有效的动作,所以爱丽丝获胜。
在第四个测试用例中,有 $$$5$$$ 堆石头,每堆石头包含 $$$8$$$ 石头。可以证明,如果两个玩家都发挥最佳,鲍勃就会获胜。