Alice 和 Bob 正在玩一个游戏,数组 $$$a$$$ 由 $$$n$$$ 非负整数组成。爱丽丝先走。
在每一回合中,当前玩家必须选择一个 $$$n$$$ 非负整数数组 $$$b = [b_1, b_2, \ldots, b_n]$$$ 满足以下条件:
- $$$0 \le b_i \le a_i$$$ 对于所有 $$$1 \le i \le n$$$;
- $$$\sum_{i=1}^n b_i \gt 0$$$ (即数组 $$$b$$$ 不完全由零组成);
- $$$b_1 \oplus b_2 \oplus \ldots \oplus b_n = 0$$$,其中 $$$\oplus$$$ 表示按位异或运算。
选择数组 $$$b$$$ 后,玩家通过对所有 $$$1 \le i \le n$$$ 执行 $$$a_i \leftarrow a_i - b_i$$$ 来更新数组 $$$a$$$。
无法执行此类操作的玩家将输掉游戏。
假设两个玩家都发挥最佳状态,确定 Alice 在第一回合中可以做出的数组 $$$b$$$ 的有效选择数量,以确保获胜。由于这个数字可能很大,因此输出对 $$$998\,244\,353$$$ 取模的答案。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出 Alice 在第一回合中可以做出的数组 $$$b$$$ 的有效选择数量,以保证获胜模 $$$998\,244\,353$$$。
示例
输入复制
51121 251 4 5 2 61107374182331 2 3
输出复制
01301
注意
在第一个测试用例中,Alice 必须选择长度为 $$$1$$$ 的数组 $$$b$$$。条件要求 $$$b_1 \le a_1$$$、$$$b_1 \gt 0$$$ 和 $$$b_1 = 0$$$。不可能同时满足 $$$b_1 \gt 0$$$ 和 $$$b_1 = 0$$$。因此,爱丽丝没有有效的行动并立即失败。答案是$$$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]$$$。现在轮到鲍勃了。与 Alice 的情况类似,Bob 必须选择 $$$b'$$$,使得 $$$b'_1 = b'_2$$$。由于$$$a_1 = 0$$$,他被迫选择$$$b'_1 = 0$$$,这意味着$$$b'_2 = 0$$$。由于有效的移动必须具有 $$$\sum b'_i \gt 0$$$,因此鲍勃没有有效的移动并失败。因此,$$$b = [1, 1]$$$ 是 Alice 的必胜棋步,答案是 $$$1$$$。