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.
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

public class Main {
	static PrintWriter out;
	static Reader in;
	public static void main(String[] args) throws IOException {
		input_output();
		Main solver = new Main();
		solver.solve();
		out.close();
		out.flush();
	}

	static long INF = (long)1e15;
	static int MAXN = (int)4e5 + 5;
	static int MOD = 998244353;
	static int q, t, n, m, k;
	static double pi = Math.PI;

	void solve() throws IOException {
		t = in.nextInt();

		while (t --> 0) {
			n = in.nextInt();

			Node[] tr = new Node[2];

			long all = 0;
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = in.nextLong();
				all += arr[i];
			}

			long ans = 0,
				 sum = 0;
			if (n <= 3) {
				int pwr = 1;
				for (int i = 1; i <= n; i++) pwr*=2;

				int tmp = 1;
				for (int j = 0; j < pwr; j++) {
					tmp = 1;
					sum = 0;
					for (int i = 0; i < n; i++) {
						if ((tmp&j) != 0) {
							sum += arr[i];
						}
						tmp*=2;
					}
					if (sum > all-sum) ans++;
				}
			} else {
				tr[0] = insertb(tr[0], new Node(arr[n-1]));
				tr[0] = insertb(tr[0], new Node(-arr[n-1]));
				tr[1] = insertb(tr[1], new Node(arr[n-1]+arr[n-2]));
				tr[1] = insertb(tr[1], new Node(-arr[n-1]+arr[n-2]));

				long[] preC = new long[n],
					   preP = new long[n];
				preC[0] = -arr[0];
				preP[0] = arr[0];
				for (int i = 1; i < n; i++) {
					preC[i] = preC[i-1]-arr[i];
					preP[i] = preP[i-1]+arr[i];
				}

				long add1 = 0,
					 add2 = 0;
				for (int i = n-2; i >= 0; i--) {
					if ( (i%2) == ((n-2)%2) ) {
						long tmp = -preC[i]-add1;
						ans += count(tr[0]) - lowerBound(tr[0], tmp+1);
						if (i != 0) {
							tmp = -(2*arr[0]+preC[i])-add1;
							ans += count(tr[0]) - lowerBound(tr[0], tmp+1);
						}

						// add
						tr[0] = erase(tr[0], lowerBound(tr[0], preP[n-1]-preP[i]-add1));
						tr[0] = erase(tr[0], lowerBound(tr[0], preP[n-1]-preP[i]-2*arr[n-1]-add1));
						if (i != 0) {
							add1 += arr[i-1]-arr[i];
							tr[0] = insertb(tr[0], new Node(preP[n-1]-((i != 1) ? preP[i-2] : 0)-add1));
							tr[0] = insertb(tr[0], new Node(preP[n-1]-((i != 1) ? preP[i-2] : 0)-2*arr[n-1]-add1));
							tr[0] = insertb(tr[0], new Node(preP[n-1]-preP[i]+arr[i-1]-arr[i]-add1));
							if (i != n-2) tr[0] = insertb(tr[0], new Node(preP[n-1]-preP[i]+arr[i-1]-arr[i]-2*arr[n-1]-add1));
						}
					} else {
						long tmp = -preC[i]-add2;
						ans += count(tr[1]) - lowerBound(tr[1], tmp+1);
						if (i != 0) {
							tmp = -(2*arr[0]+preC[i])-add2;
							ans += count(tr[1]) - lowerBound(tr[1], tmp+1);
						}

						// add
						tr[1] = erase(tr[1], lowerBound(tr[1], preP[n-1]-preP[i]-add2));
						tr[1] = erase(tr[1], lowerBound(tr[1], preP[n-1]-preP[i]-2*arr[n-1]-add2));
						if (i != 0) {
							add2 += arr[i-1]-arr[i];
							tr[1] = insertb(tr[1], new Node(preP[n-1]-((i != 1) ? preP[i-2] : 0)-add2));
							tr[1] = insertb(tr[1], new Node(preP[n-1]-((i != 1) ? preP[i-2] : 0)-2*arr[n-1]-add2));
							tr[1] = insertb(tr[1], new Node(preP[n-1]-preP[i]+arr[i-1]-arr[i]-add2));
							tr[1] = insertb(tr[1], new Node(preP[n-1]-preP[i]+arr[i-1]-arr[i]-2*arr[n-1]-add2));
						}
					}
				}

				for (int i = 1; i < n; i++) {
					if (preP[i] > all-preP[i]) ans++;
				}
			}

			ans %= MOD;
			out.println(ans);
		}
	}

	public static Random gen = new Random();

	static public class Node {
		long v;
		long priority;
		Node left, right, parent;
		int count;

		Node(long v) {
			this.v = v;
			priority = gen.nextLong();
			recalc(this);
		}
	}

	static Node recalc(Node a) {
		if (a == null) return null;
		a.count = 1;
		if (a.left != null) a.count += a.left.count;
		if (a.right != null) a.count += a.right.count;

		return a;
	}

	static int count(Node a) {
		return a == null ? 0 : a.count;
	}

	static void setParent(Node a, Node par) {
		if (a != null) a.parent = par;
	}

	static Node merge(Node a, Node b) {   //   a.values < b.values
		if (b == null) return a;
		if (a == null) return b;
		if (a.priority > b.priority) {
			setParent(a.right, null);
			setParent(b, null);
			a.right = merge(a.right, b);
			setParent(a.right, a);
			return recalc(a);
		} else {
			setParent(a, null);
			setParent(b.left, null);
			b.left = merge(a, b.left);
			setParent(b.left, b);
			return recalc(b);
		}
	}

	static Node[] split(Node a, int k) {
		if (a == null) return new Node[]{null, null};

		if (k <= count(a.left)) {
			setParent(a.left, null);
			Node[] sp = split(a.left, k);
			a.left = sp[1];
			setParent(a.left, a);
			sp[1] = recalc(a);
			return sp;
		} else {
			setParent(a.right, null);
			Node[] sp = split(a.right, k-count(a.left)-1);
			a.right = sp[0];
			setParent(a.right, a);
			sp[0] = recalc(a);
			return sp;
		}
	}

	static Node insertb(Node root, Node x) {
		int idx = lowerBound(root, x.v);
		return insert(root, idx, x);
	}

	static Node insert(Node a, int k, Node b) {
		if (a == null) return b;
		if (b.priority < a.priority) {
			if (k <= count(a.left)) {
				a.left = insert(a.left, k, b);
				setParent(a.left, a);
			} else {
				a.right = insert(a.right, k-count(a.left)-1, b);
				setParent(a.right, a);
			}
			return recalc(a);
		} else {
			Node[] ch = split(a, k);
			b.left = ch[0];
			b.right = ch[1];
			setParent(b.left, b);
			setParent(b.right, b);
			return recalc(b);
		}
	}

	static int lowerBound(Node a, long q) {
		int lcount = 0;
		while (a != null) {
			if (a.v >= q) {
				a = a.left;
			} else {
				lcount += count(a.left) + 1;
				a = a.right;
			}
		}
		return lcount;
	}

	// delete k-th (0-indexed)
	static Node erase(Node a, int k) {
		if (a == null) return null;
		if (k < count(a.left)) {
			a.left = erase(a.left, k);
			setParent(a.left, a);
			return recalc(a);
		} else if (k == count(a.left)) {
			setParent(a.left, null);
			setParent(a.right, null);
			Node aa = merge(a.left, a.right);
			disconnect(a);
			return aa;
		} else {
			a.right = erase(a.right, k-count(a.left)-1);
			setParent(a.right, a);
			return recalc(a);
		}
	}

	static void disconnect(Node a) {
		if (a == null) return;
		a.left = a.right = a.parent = null;
	}

	static class Reader {
		private InputStream mIs;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public Reader() {
			this(System.in);
		}

		public Reader(InputStream is) {
			mIs = is;
		}

		public int read() {
			if (numChars == -1) {
				throw new InputMismatchException();

			}
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = mIs.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}
	static void input_output() throws IOException {
		File f = new File("in.txt");
		if (f.exists() && !f.isDirectory()) {
			in = new Reader(new FileInputStream("in.txt"));
		} else in = new Reader();
		f = new File("out.txt");
		if (f.exists() && !f.isDirectory()) {
			out = new PrintWriter(new File("out.txt"));
		} else out = new PrintWriter(System.out);
	}
}