E. XOR Priority
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
"Did you know that the XOR symbol $$$(\oplus)$$$ is just the ADD symbol $$$(+)$$$ with a circle?"
— $$$LaTeX$$$, probably

You have $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ written from left to right. For all integers $$$1 \leq i \lt n$$$, you can either put an XOR symbol ($$$\oplus$$$) or an ADD symbol ($$$+$$$) between $$$a_i$$$ and $$$a_{i+1}$$$ to form an expression. The cost of the expression formed is the alternative result of the expression itself. Find the sum of costs from all possible $$$2^{n-1}$$$ expressions. Since the sum of costs might be too large, find the sum modulo $$$998244353$$$.

The alternative result of an expression is the result of the expression if the XOR operation is done before any other operation. For example, the alternative result of $$$5 + 3 \oplus 5$$$ is $$$5 + 6 = 11$$$ since $$$3 \oplus 5 = 6$$$ and the XOR operation has to be done before the ADD operation.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases.

The first line for each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) — the number of integers inside the expression.

The second line for each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \lt 2^{29}$$$).

It is guaranteed that the sum of $$$n$$$ from all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output a single integer — the sum of costs from all possible $$$2^{n-1}$$$ expressions, modulo $$$998244353$$$.

Example
Input
4
3
5 3 5
2
1012 1012
3
166374059 166374059 166374059
5
123456789 432101234 123454321 456787654 133769420
Output
38
2024
1
153140146
Note

Let $$$f(X)$$$ be the cost of the expression $$$X$$$.

For the first test case, there are $$$4$$$ expressions, which are $$$\{5 + 3 + 5\}, \{5 + 3 \oplus 5\}, \{5 \oplus 3 + 5\}, \{5 \oplus 3 \oplus 5\}$$$. The sum of costs is $$$f(\{5 + 3 + 5\}) + f(\{5 + 3 \oplus 5\}) + f(\{5 \oplus 3 + 5\}) + f(\{5 \oplus 3 \oplus 5\}) = 13 + 11 + 11 + 3 = 38$$$.

For the second test case, there are $$$2$$$ expressions, which are $$$\{1012 + 1012\}$$$ and $$$\{1012 \oplus 1012\}$$$.