Let \(\oplus\) denote the XOR operation.

Let \(A_i\) denote the number of stones in the \(i\)-th pile. Also, let \(S=A_1 \oplus A_2 \oplus \ldots \oplus A_N\).

The game without the bitwise OR constraint is known as Nim, and the winner can be determined as follows:

• If \(S = 0\), the second player wins; otherwise, the first player wins.

This fact can be proved by mathematical induction as follows:

• When \(S= 0\):
  • By the properties of XOR, no matter how stones are removed, it is impossible to make \(S= 0\) again.
• When \(S \neq 0\):
  • Choose one \(A_k\) such that the most significant bit of \(S\) is set. Since there are an odd number of \(A_k\) satisfying this condition, such a choice always exists.
  • Remove \(A_k - (A_k \oplus S)\) stones from the \(k\)-th pile. Since the most significant bit of \(S\) changes from \(1\) to \(0\) in \(A_k\) and there are no changes in higher bits, we have \(A_k \oplus S < A_k\), so this choice is legal.

Based on this, let us consider solving this problem.

Let \(T = A_1\ \mathrm{OR}\ A_2\ \mathrm{OR}\ \ldots \ \mathrm{OR}\ A_N \).

In fact, a similar winning strategy exists for this problem, and the winner can be determined as follows:

• If \(S = \color{red}T\), the second player wins; otherwise, the first player wins.

This fact can be proved by mathematical induction as follows:

• When \(S= T\):
  • By the properties of XOR, no matter how stones are removed, it is impossible to make \(S= T\) again.
• When \(S \neq T\):
  • Choose one \(A_k\) such that the most significant bit of \(S \oplus T\) is set. Since there are at least \(2\) values of \(A_k\) satisfying this condition, such a choice always exists.
  • Remove \(A_k - (A_k \oplus S \oplus T)\) stones from the \(k\)-th pile. Since the most significant bit of \(S \oplus T\) changes from \(1\) to \(0\) in \(A_k\) and there are no changes in higher bits, we have \(A_k \oplus S \oplus T < A_k\). Furthermore, since bits that are set in \(S \oplus T\) are set in at least two positions in \(A\), the value of \(T\) remains unchanged. Therefore, this operation is legal.

From this argument, we can conclude that we should output Bob if \(S=T\), and Alice otherwise.

By implementing the above appropriately, we can solve this problem. The time complexity is \(O(N)\) per test case.

Implementation Example (Python3)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    s, t = 0, 0
    for v in a:
        s ^= v
        t |= v
    if s == t:
        print("Bob")
    else:
        print("Alice")