E. Kia Kio and Tree of Life
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

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$$$.

Output

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$$$.

Example
Input
5
2
1 2
3
1 1 1
3
1 2 3
4
2 1 4 7
5
5 12 9 14 1
Output
6
10
40
318
2520
Note

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$$$.