题目描述

Alice 和 Bob 正在玩一个数组 $a$ 上的游戏，初始时 $a$ 包含 $n$ 个正整数，Alice 先手。

每次轮到某个玩家时，如果 $a$ 是非递减的 $^{\text{∗}}$，游戏立即结束。否则，该玩家可以从数组中选择一个元素 $x$，以及正整数 $y, z$，满足 $1 < y, z < x$ 且 $x = yz$，然后将数组中的 $x$ 替换为 $y$ 和 $z$（在 $x$ 的原位置，顺序任意）。如果没有这样的操作可执行，游戏结束。

一旦游戏结束，如果 $a$ 是非递减的，则 Bob 获胜；否则 Alice 获胜。请判断如果双方都采用最优策略，谁将获胜。

$^{\text{∗}}$ 若对于所有 $1 \leq i \leq m-1$ 都有 $a_i \leq a_{i+1}$，其中 $m$ 为 $a$ 的长度，则称 $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 获胜。

由 ChatGPT 5 翻译

来源

Codeforces 2200E，英文题名 Divisive Battle。