CF1991H Prime Split Game

Alice 和 Bob 正在玩一个有 $n$ 堆石子的游戏，第 $i$ 堆有 $a_i$ 个石子。两人轮流操作，Alice 先手。 每次操作，玩家需要完成以下三步： 1. 选择一个整数 $k$（$1 \leq k \leq \frac{n}{2}$）。注意，不同回合可以选择不同的 $k$。 2. 移除 $k$ 堆石子。 3. 再选择另外 $k$ 堆石子，将每一堆分成两堆，每一新堆的石子数都必须是质数。 无法进行操作的玩家判负。 请判断如果双方都采取最优策略，谁会获胜。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示石子的堆数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 2 \cdot 10^5$），表示每堆石子的数量。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，如果 Alice 获胜，输出 "Alice"（不含引号）；否则输出 "Bob"（不含引号）。 输出时字母大小写不敏感。例如，"alIcE"、"Alice" 和 "alice" 都视为正确答案。

在第一个测试用例中，有 $2$ 堆石子，分别有 $2$ 和 $1$ 个石子。由于 $1$ 和 $2$ 都无法分成两个质数的堆，Alice 无法进行操作，因此 Bob 获胜。 在第二个测试用例中，有 $3$ 堆石子，分别有 $3$、$5$ 和 $7$ 个石子。Alice 可以选择 $k=1$，移除 $7$ 个石子的那一堆，然后将 $5$ 个石子的那一堆分成 $2$ 和 $3$ 两堆（都是质数）。此时剩下 $3$ 堆石子，分别为 $3$、$2$ 和 $3$ 个，Bob 无法进行有效操作，因此 Alice 获胜。 在第三个测试用例中，有 $4$ 堆石子，分别为 $4$、$6$、$8$ 和 $10$ 个。Alice 可以选择 $k=2$，移除 $8$ 和 $10$ 个石子的两堆，将 $4$ 个石子的那一堆分成 $2$ 和 $2$ 两堆，将 $6$ 个石子的那一堆分成 $3$ 和 $3$ 两堆。此时 Bob 无法进行有效操作，因此 Alice 获胜。 在第四个测试用例中，有 $5$ 堆石子，每堆都是 $8$ 个。可以证明，如果双方都采取最优策略，Bob 会获胜。 由 ChatGPT 4.1 翻译