Alice 和 Bob 得到了一个二进制 $$$^{\text{*}}$$$ 字符串 $$$s$$$,长度为 $$$n$$$。他们决定在上面玩一个游戏,轮流玩,爱丽丝先走。
在每一步中,玩家必须选择一个 子序列 字符串 $$$y$$$ 的$$$^{\text{†}}$$$ 具有 奇数 反转次数$$$^{\text{‡}}$$$ 并将其删除。无法采取行动的玩家就输了。
假设双方都发挥最佳状态,确定谁赢得了比赛。
$$$^{\text{*}}$$$二进制字符串是仅由字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ 组成的字符串。
$$$^{\text{†}}$$$序列 $$$a$$$ 是字符串 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)字符从 $$$b$$$ 获得。
$$$^{\text{‡}}$$$二进制字符串 $$$s$$$ 中的反转是一对索引 $$$(i, j)$$$,使得 $$$i \lt j$$$ 和 $$$s_i = \texttt{1}$$$ 和 $$$s_j = \texttt{0}$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。每个测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 二进制字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。保证 $$$s$$$ 的每个字符都是 $$$\texttt{0}$$$ 或 $$$\texttt{1}$$$。
保证所有测试用例的$$$n$$$总和不超过$$$2\cdot10^5$$$。
输出
对于每个测试用例,如果 Alice 赢得了游戏,则打印 $$$\texttt{Alice}$$$,否则打印 $$$\texttt{Bob}$$$。
示例
输入复制
3510101401006011001
输出复制
AliceAliceBob
注意
对于第一个测试用例,Alice 可以选择整个字符串,因为它有奇数个反转。现在,鲍勃只剩下一根空弦,他无法采取行动。因此,爱丽丝获胜。
对于第二个测试用例,Alice 可以选择索引 $$$1$$$、$$$2$$$ 和 $$$4$$$ 处的字符形成的子序列,即 $$$\texttt{010}$$$。然后 Bob 留下索引 $$$3$$$ 处的字符,即 $$$\texttt{0}$$$,它有 $$$0$$$ 反转(偶数)。因此,Bob 无法选择具有奇数个反转的子序列,因此 Alice 获胜。
对于第三个测试用例,可以证明无论 Alice 的第一步如何,Bob 都可以保证获胜。