Chef has an array A of length N.

He can modify this array by applying a special operation any number of times. In one operation, he can:
Select two indices i and j (1≤ i < j ≤ |A|).
Append $A_{i} \oplus A_{j}$ to the end of the array, where $\oplus$ denotes the [bitwise XOR operation]
Remove A_{i} and A_{j} from the array.

Chef wants to maximize the product of all the elements of the array after applying these operations.

Help Chef determine the maximum product he can achieve by applying this operation any (possibly zero) number of times. As this number can be large, print it modulo 998244353.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains one integer N — the number of elements in the array.
• The second line consists of $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$ denoting the elements of the array initially.

------ Output Format ------

For each test case, output the maximum product he can achieve modulo 998244353.

------ Constraints ------

$1 ≤ T ≤ 5\cdot 10^{4}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------
3
4
1 2 1 2
2
3 3
2
2 1

----- Sample Output 1 ------
9
9
3

----- explanation 1 ------
Test case $1$: Chef can make the following operations:
- Operation $1$: Choose $i = 1$ and $j = 2$, append $A_{1}\oplus A_{2} = 1\oplus 2 = 3$ to the end of the array and remove elements $A_{1}$ and $A_{2}$. Thus, the array becomes $[1, 2, 3]$.
- Operation $2$: Choose $i = 1$ and $j = 2$, append $A_{1}\oplus A_{2} = 1\oplus 2 = 3$ to the end of the array and remove elements $A_{1}$ and $A_{2}$. Thus, the array becomes $[3, 3]$.

The product of all elements of the array is $3\times 3 = 9$. It can be shown that this is the maximum product that can be obtained by applying any number of operations on the array.

Test case $2$: The product of all elements of the array is $3\times 3 = 9$. It can be shown that this is the maximum product that can be obtained by applying any number of operations on the array.
Thus, Chef does not need to perform any operations.

Test case $3$: Chef can make the following operation:
- Operation $1$: Choose $i = 1$ and $j = 2$, append $A_{1}\oplus A_{2} = 1\oplus 2 = 3$ to the end of the array and remove elements $A_{1}$ and $A_{2}$. Thus, the array becomes $[3]$.

The product of all elements is $3$. It can be shown that this is the maximum product that can be obtained by applying any number of operations on the array.

见题面

见题面