You are given an array A of size N.

A partitioning of the array A is the splitting of A into one or more non-empty contiguous subarrays such that each element of A belongs to exactly one of these subarrays.

Find the number of ways to partition A such that the parity of the sum of elements within the subarrays is alternating. In other words, if S_{i} denotes the sum of the elements in the i-th subarray, then either
S_{1} is odd, S_{2} is even, S_{3} is odd and so on.
or S_{1} is even, S_{2} is odd, S_{3} is even and so on.

For example if A = [1, 2, 3, 3, 5]. One way to partition A is [1, 2] [3, 3] [5]. Another way to partition A is [1] [2] [3] [3, 5]. Note that there exists more ways to partition this array.

Since the answer may be large, output it modulo 998244353.

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

• The first line contains a single integer T - the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N - the size of the array A.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$ denoting the array A.

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

For each test case, output the answer modulo 998244353.

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

$1 ≤ T ≤ 10000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ A_{i} ≤ 10^{9} $
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------
3
3
1 2 3
4
4 4 4 4
5
1 2 3 3 5
----- Sample Output 1 ------
2
1
5

----- explanation 1 ------
Test case 1: The array can be partitioned as follows
- $[1] [2] [3]$
- $[1, 2, 3]$

Test case 2: The array can be partitioned as follows
- $[4, 4, 4, 4]$

见题面

见题面