CF2241F.A Bit Odd

Alice and Bob have got a binary$^{\text{∗}}$ string $s$ of length $n$. They have decided to play a game on it, taking turns alternately, with Alice moving first.

In each move, the player must select a subsequence$^{\text{†}}$ which has an odd number of inversions$^{\text{‡}}$ and delete it. The player who cannot make a move loses.

Determine who wins the game, assuming both players play optimally.

$^{\text{∗}}$A binary string is a string that consists only of the characters $\texttt{0}$ and $\texttt{1}$.

$^{\text{†}}$A sequence $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly zero or all) characters.

$^{\text{‡}}$An inversion in a binary string $s$ is a pair of indices $(i, j)$ such that $i \lt j$ and $s_i = \texttt{1}$ and $s_j = \texttt{0}$.

爱丽丝和鲍勃得到了一个长度为 $n$ 的二进制$^{\text{∗}}$字符串 $s$。他们决定在该字符串上进行一场游戏，轮流行动，爱丽丝先手。

在每一轮中，当前玩家必须选择一个具有奇数个逆序对$^{\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}$。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of each test case follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of the binary string $s$.

The second line of each test case contains a binary string $s$ of length $n$. It is guaranteed that each character of $s$ is either $\texttt{0}$ or $\texttt{1}$.

It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot10^5$.

第一行包含一个整数 $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$。

For each test case, print $\texttt{Alice}$ if Alice wins the game and $\texttt{Bob}$ otherwise.

对于每个测试用例，如果 Alice 获胜则输出 $\texttt{Alice}$，否则输出 $\texttt{Bob}$。

For the first test case, Alice can choose the entire string as it has an odd number of inversions. Now, Bob is left with an empty string, and he cannot make a move. Thus, Alice wins.

For the second test case, Alice can choose the subsequence formed by the characters at indices $1$, $2$, and $4$, i.e., $\texttt{010}$. Bob is then left with the character at index $3$, namely $\texttt{0}$, which has $0$ inversions (an even number). Therefore, Bob cannot choose a subsequence with an odd number of inversions, so Alice wins.

For the third test case, it can be shown that Bob can guarantee a win irrespective of Alice's first move.

对于第一个测试用例，Alice 可以选择整个字符串，因为该字符串具有奇数个逆序对。此时 Bob 面对的是一个空字符串，无法进行任何操作。因此 Alice 获胜。

对于第二个测试用例，Alice 可以选择由下标 $1$、$2$ 和 $4$ 处的字符构成的子序列，即 $\texttt{010}$。此时 Bob 剩余的字符位于下标 $3$ 处，即 $\texttt{0}$，其逆序对数量为 $0$（偶数）。因此 Bob 无法选出一个具有奇数个逆序对的子序列，故 Alice 获胜。

对于第三个测试用例，可以证明：无论 Alice 的第一步如何操作，Bob 均能确保获胜。