Sum of XOR of All Subsets

You are given T homework assignments. Each assignment consists of a pair (n, V) where n is the size of a set V containing n integers. For each assignment, you need to compute the sum of the XOR of all subsets of V modulo 998244353.

Formally, for a set \(V\) with \(n\) elements, you are to calculate:

[ \text{ans} \equiv \sum_{S \subseteq V} \bigoplus_{s \in S} s \pmod{998244353} ]

Here, \(\bigoplus\) denotes the bitwise XOR operation and the empty subset has an XOR sum of 0.

Hint: It can be proven that the answer is equal to \(2^{n-1} \times (v_1 \lor v_2 \lor \cdots \lor v_n)\) when \(n > 0\), where \(\lor\) is the bitwise OR operation.

inputFormat

The first line contains an integer \(T\) (the number of homework assignments).

For each assignment, the input is given as follows:

1. An integer \(n\) representing the number of elements in the set \(V\).
2. A line with \(n\) space-separated integers denoting the elements of the set \(V\).

outputFormat

For each assignment, output a single line containing the required answer modulo 998244353.

sample

1
3
1 2 3

12