Description

Input

Each test contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^4$) — the number of test cases.

The first line contains an integer $n$ ($1\le n\le 10^6$) — the length of $a$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^6 \leq a_i \leq 10^6$) — the given sequence.

It's guaranteed that the sum of $n$ does not exceed $10^6$.

Output

For each test case, print a line containing a single integer — the answer modulo $998\,244\,353$.

4
7
80 59 100 -52 -86 -62 75
8
-48 -14 -26 43 -41 34 13 55
1
74
20
56 -60 62 13 88 -48 64 36 -10 19 94 25 -69 88 87 79 -70 74 -26 59
 
 
 
 

5924
2548
148
98887

Note

In the second test case, for the subsequence $[-26,43,-41,34,13]$, when $q=5$, $s=2$, $t=5$, $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$.

In the third test case, there is only one non-empty consecutive subsequence $[74]$. When $q=1$, $s=1$, $t=1$, $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 148$.