CF2268E.Kia Kio and Tree of Life

After unlocking the crystal terminal, Kia and Kio discovered the blueprint for the kingdom's forgotten heart: a digital Tree of Life, seeded by the array $a_1, a_2, \ldots, a_n$.

To restore its pulse, they had to weave every possible incarnation of the Tree together. For any continuous segment, Kia would gently select an index $i$ to plant the root. Trusting her vision, Kio would carefully weave the branches of life — crafting the left subtree from the preceding segment $[1, i-1]$ and the right subtree from the succeeding segment $[i+1, n]$.

Once a Tree of Life bloomed, its vital resonance, $f(\text{tree})$, was defined by its bonds. If one were to sever any of the $n-1$ delicate branches, the Tree would split into two disconnected halves, releasing an energy of $X+Y$, where $X$ and $Y$ are the bitwise XOR sums of the array elements remaining in the first and second halves, respectively.

The total power of the Tree, $f(\text{tree})$, is the sum of these released energies across all $n-1$ branches.

Kia wanted to know the ultimate vital force they could awaken. Help them compute the total sum of $f(\text{tree})$ across every valid Tree of Life born from their shared bond, modulo $998\,244\,353$.

解锁水晶终端后，Kia 和 Kio 发现了王国被遗忘之心的蓝图：一棵由数组 $a_1, a_2, \ldots, a_n$ 初始化的数字生命之树（Tree of Life）。

为恢复其脉动，他们必须将生命之树所有可能的形态编织在一起。对于任意一个连续子段，Kia 会轻柔地从中选定一个下标 $i$ 作为根节点；凭借她敏锐的直觉，Kio 则会细致地编织生命的枝杈——用前缀子段 $[1, i-1]$ 构建左子树，用后缀子段 $[i+1, n]$ 构建右子树。

一旦一棵生命之树绽放，其生命共振值 $f(\text{tree})$ 即由其所有“纽带”（即边）所定义。若切断任意一条 $n-1$ 条纤细的树枝，该树便分裂为两个互不连通的部分，并释放能量 $X+Y$，其中 $X$ 与 $Y$ 分别为第一部分和第二部分中剩余数组元素的按位异或（XOR）和。

整棵树的总能量 $f(\text{tree})$ 即为对全部 $n-1$ 条边分别切断后所释放能量之和。

Kia 想知道他们所能唤醒的生命之力的终极上限。请帮助他们计算：对所有由该数组生成的有效生命之树（即所有合法的根选择方式所构建的树），其 $f(\text{tree})$ 值之总和，结果对 $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 2\cdot10^5$) — the size of the array.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \lt 2^{18}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

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

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$）—— 表示数组的大小。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \lt 2^{18}$）。

保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。

For each test case, print a single integer — the total sum of $f(\text{tree})$ across all valid Trees of Life, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——所有有效的“生命之树”（Trees of Life）的 $f(\text{tree})$ 值之和，对 $998\,244\,353$ 取模。

For the first test case, $n=2$ and $a = [1,2]$. There are two valid trees that can be constructed: one with $a_1$ as the root and $a_2$ as the right child, and one with $a_2$ as the root and $a_1$ as the left child.

In both trees, severing the single branch leaves two components with XOR sums $X=1$ and $Y=2$. Thus, the value for each tree becomes $1 + 2 = 3$. The total energy accumulated across both Trees of Life is $3+3=6$.

For the second test case, $n=3$ and $a = [1,1,1]$.

There are $5$ valid trees that can be constructed:

• Root is $1$: ${(1,2), (2,3)}$, ${(1, 3), (2, 3)}$;
• Root is $2$: ${(1,2), (2,3)}$;
• Root is $3$: ${(1,3), (1,2)}$, ${(2, 3), (1, 2)}$.

All trees are just a path with three vertices, and severing a single branch leaves two components with XOR sums $X=1$ and $Y=0$. So the value for each tree becomes $2$. The total energy accumulated across all five Trees of Life is $5\cdot 2=10$.

对于第一个测试用例，$n=2$ 且 $a = [1,2]$。可以构造出两棵合法的树：一棵以 $a_1$ 为根、$a_2$ 为右子节点；另一棵以 $a_2$ 为根、$a_1$ 为左子节点。

在这两棵树中，切断唯一的边后均得到两个连通分量，其异或和分别为 $X=1$ 和 $Y=2$。因此，每棵树的值均为 $1 + 2 = 3$。所有“生命之树”的总能量为 $3+3=6$。

对于第二个测试用例，$n=3$ 且 $a = [1,1,1]$。

可以构造出 $5$ 棵合法的树：

• 根节点为 $1$：$\{(1,2), (2,3)\}$，$\{(1, 3), (2, 3)\}$；
• 根节点为 $2$：$\{(1,2), (2,3)\}$；
• 根节点为 $3$：$\{(1,3), (1,2)\}$，$\{(2, 3), (1, 2)\}$。

所有树均为包含三个顶点的一条路径，切断任意一条边后均得到两个连通分量，其异或和分别为 $X=1$ 和 $Y=0$。因此，每棵树的值均为 $2$。所有五棵“生命之树”的总能量为 $5\cdot 2=10$。