Let $$$\operatorname{inv}(s)$$$ denote the number of inversions in string $$$s$$$. Suppose the initial state is in state three. Alice chooses to remove subsequence $$$a$$$, leaving subsequence $$$b$$$. Since $$$s$$$ is in state three, any $$$0$$$ in $$$s$$$ has an even number of 1s before it, and any $$$1$$$ has an even number of 0s after it. According to the problem constraints, we must have $$$\operatorname{inv}(a) \equiv 1 \pmod 2$$$. We need to prove that subsequence $$$b$$$ cannot be in state three.

Let $$$\operatorname{inv}(a,b)$$$ denote the number of cross-inversions between $$$a$$$ and $$$b$$$. Cross-inversions fall into two categories:

• A $$$1$$$ is in $$$a$$$ and a $$$0$$$ is in $$$b$$$, with the $$$1$$$ appearing before the $$$0$$$.
• A $$$1$$$ is in $$$b$$$ and a $$$0$$$ is in $$$a$$$, with the $$$1$$$ appearing before the $$$0$$$.

When splitting $$$s$$$ into $$$a$$$ and $$$b$$$, the total number of inversions satisfies $$$\operatorname{inv}(s)=\operatorname{inv}(a)+\operatorname{inv}(b)+\operatorname{inv}(a,b)$$$.

We will use proof by contradiction. Assume that $$$b$$$ is also in state three. Let's analyze the parity of $$$\operatorname{inv}(a,b)$$$:

• For the first type of cross-inversion, consider each $$$0$$$ in $$$b$$$: in the original sequence $$$s$$$, it has an even number of $$$1$$$s before it. In $$$b$$$, since $$$b$$$ is also assumed to be in state three, it also has an even number of $$$1$$$s before it. Since subtracting two even numbers yields an even number, the number of $$$1$$$s before it that belong to $$$a$$$ must also be even. Summing these even counts across all $$$0$$$s in $$$b$$$ still results in an even number.
• For the second type of cross-inversion, consider each $$$1$$$ in $$$b$$$: in the original sequence $$$s$$$, it has an even number of $$$0$$$s after it. In $$$b$$$, since $$$b$$$ is in state three, it also has an even number of $$$0$$$s after it. By the same logic, the number of $$$0$$$s after it that belong to $$$a$$$ must be even. Summing these up across all $$$1$$$s in $$$b$$$ gives an even number.

Since both types of cross-inversions have an even count, their sum, $$$\operatorname{inv}(a,b)$$$, must be even.

Substituting these parities back into our formula:

This implies that $$$\operatorname{inv}(b)$$$ must be odd, meaning $$$b$$$ transitions into state one. This contradicts our assumption that $$$b$$$ is in state three. Therefore, subsequence $$$b$$$ cannot be in state three, meaning any move Alice makes will leave the sequence in either state one or state two. Thus, if $$$s$$$ starts in state three, Bob always wins.

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200005;
int _, n, sum[N], tot;
string s;
bool flag;
signed main() {
    cin >> _;
    while (_--) {
        cin >> n >> s;
        s = " " + s;
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] ^ 48);
        tot = 0;
        for (int i = 1; i <= n; i++) if (s[i] == '0') tot += sum[i];
        if (tot & 1) {
            puts("Alice");
            continue;
        }
        flag = 0;
        for (int i = 1; i <= n; i++) {
            if (s[i] == '0' && (sum[i] & 1)) {
                flag = 1;
                break;
            } else if (s[i] == '1' && ((n - i - sum[n] + sum[i]) & 1)) {
                flag = 1;
                break;
            }
        }
        puts(flag ? "Alice" : "Bob");
    }
    return 0;
}