CF2239A.Nim Game Is XOR Game

Alice and Bob are playing a game with an array $a$ consisting of $n$ non-negative integers. Alice goes first.

In each turn, the current player must choose an array of $n$ non-negative integers $b = [b_1, b_2, \ldots, b_n]$ that satisfies the following conditions:

1. $0 \le b_i \le a_i$ for all $1 \le i \le n$;
2. $\sum_{i=1}^n b_i \gt 0$ (i.e. the array $b$ does not consist entirely of zeros);
3. $b_1 \oplus b_2 \oplus \ldots \oplus b_n = 0$, where $\oplus$ denotes the bitwise XOR operation.

After choosing the array $b$, the player updates the array $a$ by performing $a_i \leftarrow a_i - b_i$ for all $1 \le i \le n$.

The player who cannot perform such an operation loses the game.

Determine the number of valid choices for the array $b$ that Alice can make on her first turn to guarantee a win, assuming both players play optimally. Since this number may be large, output the answer modulo $998\,244\,353$.

爱丽丝和鲍勃正在用一个包含 $n$ 个非负整数的数组 $a$ 进行一场游戏。爱丽丝先手。

在每一轮中，当前玩家必须选择一个由 $n$ 个非负整数构成的数组 $b = [b_1, b_2, \ldots, b_n]$，该数组需满足以下条件：

1. 对所有 $1 \le i \le n$，有 $0 \le b_i \le a_i$；
2. $\sum_{i=1}^n b_i \gt 0$（即数组 $b$ 不全为零）；
3. $b_1 \oplus b_2 \oplus \ldots \oplus b_n = 0$，其中 $\oplus$ 表示按位异或运算。

选定数组 $b$ 后，玩家将数组 $a$ 更新为：对所有 $1 \le i \le n$，执行 $a_i \leftarrow a_i - b_i$。

无法执行上述操作的玩家判负。

假设双方均以最优策略进行游戏，求爱丽丝在第一回合中能选择的、可确保获胜的合法数组 $b$ 的数量。由于该数量可能很大，请将答案对 $998\,244\,353$ 取模后输出。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \lt 2^{30}$) — the contents of the array $a$

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^6$）——数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \lt 2^{30}$）——数组 $a$ 的内容。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

For each test case, output the number of valid choices for the array $b$ that Alice can make on her first turn to guarantee a win modulo $998\,244\,353$.

对于每个测试用例，输出 Alice 在第一回合能做出的、可保证获胜的数组 $b$ 的合法选择数目，结果对 $998\,244\,353$ 取模。

In the first test case, Alice must choose an array $b$ of length $1$. The conditions require $b_1 \le a_1$, $b_1 \gt 0$, and $b_1 = 0$. It is impossible to satisfy $b_1 \gt 0$ and $b_1 = 0$ simultaneously. Thus, Alice has no valid moves and loses immediately. The answer is $0$.

In the second test case, $a = [1, 2]$. Alice must choose $b = [b_1, b_2]$. The condition $b_1 \oplus b_2 = 0$ implies that $b_1 = b_2$. Since $0 \le b_1 \le 1$ and $0 \le b_2 \le 2$, and the array $b$ cannot consist entirely of zeros, the only valid choice is $b = [1, 1]$. If Alice chooses $b = [1, 1]$, the array updates to $a = [1-1, 2-1] = [0, 1]$. Now it is Bob's turn. Similar to Alice's situation, Bob must choose $b'$ such that $b'_1 = b'_2$. Since $a_1 = 0$, he is forced to pick $b'_1 = 0$, which means $b'_2 = 0$. Since a valid move must have $\sum b'_i \gt 0$, Bob has no valid moves and loses. Therefore, $b = [1, 1]$ is a winning move for Alice, and the answer is $1$.

在第一个测试用例中，Alice 必须选择一个长度为 $1$ 的数组 $b$。条件要求 $b_1 \le a_1$、$b_1 \gt 0$ 且 $b_1 = 0$。但 $b_1 \gt 0$ 与 $b_1 = 0$ 不可能同时成立。因此，Alice 没有合法操作，立即失败。答案为 $0$。

在第二个测试用例中，$a = [1, 2]$。Alice 必须选择 $b = [b_1, b_2]$。条件 $b_1 \oplus b_2 = 0$ 意味着 $b_1 = b_2$。由于 $0 \le b_1 \le 1$ 且 $0 \le b_2 \le 2$，且数组 $b$ 不能全为零，唯一合法的选择是 $b = [1, 1]$。若 Alice 选择 $b = [1, 1]$，则数组更新为 $a = [1-1, 2-1] = [0, 1]$。此时轮到 Bob 行动。与 Alice 的情形类似，Bob 必须选择满足 $b'_1 = b'_2$ 的 $b'$。由于 $a_1 = 0$，他被迫选择 $b'_1 = 0$，从而 $b'_2 = 0$。而合法操作要求 $\sum b'_i \gt 0$，因此 Bob 没有合法操作，失败。故 $b = [1, 1]$ 是 Alice 的必胜操作，答案为 $1$。