The two versions of the problem are different. You may want to read both versions. You can make hacks only if both versions are solved.

You are given an array $a$ of length $n$. Start with $c = 0$. Then, for each $i$ from $1$ to $n$ (in increasing order) do exactly one of the following:

• Option $1$: set $c$ to $c + a_i$.
• Option $2$: set $c$ to $|c + a_i|$, where $|x|$ is the absolute value of $x$.

Let the maximum final value of $c$ after the procedure described above be equal to $k$. Find the number of unique procedures that result in $c = k$. Two procedures are different if at any index $i$, one procedure chose option $1$ and another chose option $2$, even if the value of $c$ is equal for both procedures after that turn.

Since the answer may be large, output it modulo $998\,244\,353$.

Input

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

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$).

The sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

Output

For each test case, output a single integer — the number of unique procedures that result in $c = k$, modulo $998\,244\,353$.

Note

In the first test case, it can be shown that our maximal final value of $c$ is $3$. There are $12$ ways to achieve this because in order to get $3$, we have to take absolute value at indices $2$ or $4$, or both, resulting in $3$ ways. For the other two indices, it doesn't change the value whether we take absolute value or not, so we have $2 \cdot 2 = 4$ ways for them. In total, we have $3 \cdot 4 = 12$ ways.

In the second test case, taking the absolute value will never change anything, so we can either take absolute value or not, for every index. This gives us $2^8 = 256$ possible ways.