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.

Magnitude (Hard Version)

Examples