题目描述

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

每次轮到某个玩家时，如果 $a$ 是非递减的，游戏立即结束。

否则，该玩家可以从数组中选择一个元素 $x$，以及正整数 $y, z$，满足 $1 < y, z < x$ 且 $x = y\cdot z$，然后将数组中的 $x$ 替换为 $y$ 和 $z$（在 $x$ 的原位置，顺序任意）。如果没有这样的操作可执行，游戏结束。

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

若对于所有 $1 \leq i \leq n-1$ 都有 $a_i \leq a_{i+1}$，其中 $n$ 为 $a$ 的长度，则称 $a$ 是非递减的。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 表示测试数据组数。对于每一组数据：

• 第一行输入一个整数 $n$。
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

对于每个测试用例，输出一行。如果 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

6
10
233578 844736 672937 29676 147181 375510 438992 380077 666786 702097
10
280290 192354 346191 281878 904941 742320 803910 644797 254391 910107
10
3475 71031 87623 103939 130245 453342 537904 672233 870919 934507
10
425546 36314 392452 212095 237314 816388 919654 318641 434699 908743
10
75937 138077 150551 193883 550111 660769 727843 732187 736511 771299
10
688201 173501 59209 503707 296773 686897 63487 712981 93199 605719

Alice
Alice
Bob
Alice
Bob
Alice

提示

样例解释

• 在第一个测试用例中，如果双方都采用最优策略，Alice 获胜。

• 在第二个测试用例中，无论 Alice 怎么操作，Bob 都必胜。

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

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

数据范围

对于 $100\%$ 的数据满足：$1 \leq t \leq 10^4$，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^6$。所有测试用例中 $n$ 之和不超过 $10^5$。

• 子任务 1（30 分）：$n \le 10, a_i \le 20$。
• 子任务 2（30 分）：$a_i$ 全部都是质数，或者数组已经有序。
• 子任务 3（40 分）：无特殊限制。