In the 2050 Conference, some people from the competitive programming community meet together and are going to take a photo. The n people form a line. They are numbered from 1 to n from left to right. Each of them either holds a cardboard with the letter 'C' or a cardboard with the letter 'P'.

Let C=\\{c_1,c_2,...,c_m\} (c_1<c_2<… <c_m) be the set of people who hold cardboards of 'C'. Let P=\\{p_1,p_2,...,p_k\} (p_1<p_2<… <p_k) be the set of people who hold cardboards of 'P'. The photo is good if and only if it satisfies the following constraints: 

  1. C∪ P=\{1,2,...,n\} 
  2. C∩ P =∅ . 
  3. c_i-c_{i-1}≤ c_{i+1}-c_i(1< i <m). 
  4. p_i-p_{i-1}≥ p_{i+1}-p_i(1< i <k). 



Given an array a_1,…, a_n, please find the number of good photos satisfying the following condition: $$$∑_{x∈ C} a_x < ∑_{y∈ P} a_y.$$$

The answer can be large, so output it modulo 998 244 353. Two photos are different if and only if there exists at least one person who holds a cardboard of 'C' in one photo but holds a cardboard of 'P' in the other.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 200 000). Description of the test cases follows.

The first line of each test case contains a single integer n (1≤ n≤ 200 000).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 200 000.

Output

For each test case, output the answer modulo 998 244 353 in a separate line.

Example

Input


3
5
2 1 2 1 1
4
9 2 2 2
1
998244353


Output


10
7
1

Note

For the first test case, there are 10 possible good photos satisfying the condition: PPPPP, CPPPP, PCPPP, CCPPP, PCCPP, PCPCP, PPPPC, CPPPC, PCPPC, PPPCC.

For the second test case, there are 7 possible good photos satisfying the condition: PPPP, PCPP, PCCP, PPPC, PCPC, PPCC, PCCC.
/*
bts songs to dance to:
I need U
Run
ON
Filter
I'm fine
 */
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1517E
{
    static final long MOD = 998244353L;
    public static void main(String hi[]) throws Exception
    {
        FastScanner infile = new FastScanner();
        int T = infile.nextInt();
        StringBuilder sb = new StringBuilder();
        while(T-->0)
        {
            int N = infile.nextInt();
            int[] arr = infile.nextInts(N);
            if(N < 6)
            {
                int res = 0;
                long total = 0L;
                for(int x: arr)
                    total += x;
                for(int mask=0; mask < 1<<N; mask++)
                {
                    long sum = 0L;
                    ArrayList<Integer> lsC = new ArrayList<Integer>();
                    ArrayList<Integer> lsP = new ArrayList<Integer>();
                    for(int b=0; b < N; b++)
                    {
                        if((mask&(1<<b)) > 0)
                        {
                            lsC.add(b);
                            sum += arr[b];
                        }
                        else
                            lsP.add(b);
                    }
                    boolean works = true;
                    for(int i=1; i < lsC.size()-1; i++)
                        if(lsC.get(i)-lsC.get(i-1) > lsC.get(i+1)-lsC.get(i))
                            works = false;
                    for(int i=1; i < lsP.size()-1; i++)
                        if(lsP.get(i)-lsP.get(i-1) < lsP.get(i+1)-lsP.get(i))
                            works = false;
                    if(works && sum < total-sum)
                    {
                        res++;
                    }
                }
                sb.append(res+"\n");
                continue;
            }
            long res = 0L;
            //general cases
            for(int a=0; a < 2; a++)
                for(int b=N-1; b >= N-2; b--)
                {
                    long extraP = a == 0 ? 0L : arr[0];
                    long extraC = b == N-1 ? 0L : arr[N-1];
                    long temp = solve(arr, a, b, extraP, extraC);
                    if(debug)
                        System.out.println(a+" "+b+" gives "+temp);
                    res += temp;
                    if(res >= MOD)
                        res -= MOD;
                }
            //P..C
            long total = 0L;
            for(int x: arr)
                total += x;
            long prefix = 0L;
            for(int i=0; i < N; i++)
            {
                prefix += arr[i];
                if(prefix > total-prefix)
                    res++;
            }
            res %= MOD;
            sb.append(res+"\n");
        }
        System.out.print(sb);
    }
    static boolean debug = false;
    public static long solve(int[] input, int L, int R, long eP, long eC)
    {
        int[] arr = new int[R-L+1];
        for(int i=L; i <= R; i++)
            arr[i-L] = input[i];
        int N = arr.length;
        //CC...C[PCPC...PCP]PPP
        long[] psums = new long[N];
        long[] alternate0 = new long[N];
        long[] alternate1 = new long[N];
        psums[0] = alternate0[0] = arr[0];
        for(int i=1; i < N; i++)
        {
            psums[i] = psums[i-1]+arr[i];
            alternate0[i] = alternate0[i-1];
            alternate1[i] = alternate1[i-1];
            if((i&1) == 0)
                alternate0[i] += arr[i];
            else
                alternate1[i] += arr[i];
        }
        if(debug && L == 1 && R == 5)
        {
            print(psums);
            print(alternate0);
            print(alternate1);
        }
        //must start with C, end with P
        long res = 0L;
        for(int a=1; a < N; a++)
        {
            long[] alternate = alternate1;
            if((a&1) == 0)
                alternate = alternate0;
            int low = a;
            int high = N-1;
            if((a&1) != (high&1))
                high--;
            while(low != high)
            {
                int mid = (low+high+1)>>1;
                //sum of P's
                int temp = mid+1;
                if((a&1) != (mid&1))
                    temp = mid;
                long allP = query(a, mid, alternate)+query(temp, N-1, psums);
                long allC = psums[N-1]-allP;
                allP += eP;
                allC += eC;
                if(debug && L == 1 && R == 5)
                    System.out.println(allP+" "+allC);
                if(allP > allC)
                    low = mid;
                else
                    high = mid-1;
            }
            if(psums[a-1]+eC >= query(a, N-1, psums)+eP)
                continue;
            res += (low-a)/2+1;
            if(res >= MOD)
                res -= MOD;
        }
        return res;
    }
    public static long query(int L, int R, long[] dp)
    {
        long res = dp[R];
        if(L > 0)
            res -= dp[L-1];
        return res;
    }
    public static void print(long[] arr)
    {
        //for debugging only
        for(long x: arr)
            out.print(x+" ");
        out.println();
    }
}
/*
1
6
20908065 600120285 164191625 49959421 517451054 162920537

PPPPPP
PPPPPC
PPPPCC
PPPCCC

P[CPPPP]
P[CPCPP]

CPPPPP
CCPPPP
CPCPPP
CCPCPP
CPCPCP
CPPPPC
CPCPPC

 */
class FastScanner
{
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }

    public int nextInt() {
        return (int) nextLong();
    }

    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }

    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }

    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }

    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}