Obviously, an inversion consists of a $$$1$$$ and a $$$0$$$ that comes after it. The reduction in the total number of inversions after an operation equals the number of inversions where at least one of its elements ($$$0$$$ or $$$1$$$) is deleted. By the Inclusion-Exclusion Principle, this equals (inversions with deleted $$$1$$$s) + (inversions with deleted $$$0$$$s) - (inversions with both $$$0$$$ and $$$1$$$ deleted).

Let's analyze the parity of these three terms:

• Inversions with deleted $$$1$$$s: This is equal to the sum of inversions contributed by each deleted $$$1$$$ in the chosen subsequence. Since $$$s$$$ is in state three, each $$$s_i$$$ contributes an even number of inversions. Thus, this term is the sum of several even numbers, which is even.
• Inversions with deleted $0$s: By the same logic, this term is also even.
• Inversions with both $$$0$$$ and $$$1$$$ deleted: This is simply the number of inversions within the chosen deleted subsequence itself. According to the problem statement, this must be odd.

In conclusion, the reduction in the total number of inversions after Alice's move must be odd. Since the total number of inversions in state three is initially even, the sequence will have an odd number of inversions after her move. This guarantees that Bob receives state one (an N-state), so he can immediately win by removing the entire sequence.

#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;
}