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

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