F. Self-Produced Sequences
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Let's call an integer sequence self-produced if for every $$$i$$$ ($$$1 \le i \le n$$$) at least one of the following conditions holds:

  • $$$a_i$$$ is equal to the sum of the elements on the left (i. e. $$$a_i = \displaystyle\sum\limits_{j = 1}^{i - 1} a_j$$$);
  • $$$a_i$$$ is equal to the sum of the elements on the right (i. e. $$$a_i = \displaystyle\sum\limits_{j = i + 1}^{n} a_j$$$).

Note that $$$0$$$ at the beginning/end of the sequence is also considered valid.

You are given an integer array $$$a$$$ of size $$$n$$$. Your task is to calculate the number of self-produced subsequences of the array $$$a$$$. Since the answer might be large, print it modulo $$$998244353$$$. Two subsequences are different if the indices of chosen elements are different.

Input

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the number of self-produced subsequences of the array $$$a$$$ taken modulo $$$998244353$$$.

Example
Input
5
3
1 1 2
2
0 0
5
0 1 0 1 0
6
1 0 2 2 1 1
11
2 0 3 1 0 0 2 3 0 3 2
Output
2
4
12
8
41