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.
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=998244353LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

ll N; vector<ll> a;
vector<ll> ps; vector<ll> pspar;

ll PS(ll l, ll r)
{	
	if(r<l) {return 0LL;}
	if(l==0) {return ps[r];}
	else {return (ps[r]-ps[l-1]);}
}

ll PSPAR(ll l, ll r, bool even) 
{
	if(r<l) {return 0LL;}
	if(even && r%2!=0) {r--;}
	if(!even && r%2==0) {r--;}
	if(even && l%2==0) {l--;}
	if(!even && l%2!=0) {l--;}
	if(l>=1) {return (pspar[r]-pspar[l-1]);} else {return pspar[r];}
}

ll solve(ll l, ll r, ll minsumP)
{
	if(l>r) {if(minsumP<=0) {return 1LL;} else {return 0LL;}}
	ll ans=0LL;
	REP(i,l-1,r+1) //where do C...C end
	{
		if(PS(i+1,r)<minsumP) {return ans;}
		ll lo = i+1; ll hi=r+1; if((hi-i)%2==0) {hi--;}
		while(lo<hi)
		{
			ll mid = (lo+hi)/2LL; if((mid-i)%2==0) {mid++;}
			if(PS(mid,r)+PSPAR(i+1,mid-1,mid%2==0)>=minsumP) {lo=mid;} else {hi=mid-2;}
		}
		ans+=((lo-i+1LL)/2LL);
		ans%=mod;
	}
	return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll T; cin>>T;
	REP(t,0,T)
	{
		cin>>N; 
		a.clear(); ps.clear(); pspar.clear();
		In(a,N); ll sum=0LL; REP(i,0,N) {sum+=a[i];}
		ll cursum=0LL; REP(i,0,N) {cursum+=a[i]; ps.pb(cursum);}
		ll sumeven=0LL; ll sumodd=0LL;
		REP(i,0,N) {if(i%2==0) {sumeven+=a[i]; pspar.pb(sumeven);} else {sumodd+=a[i]; pspar.pb(sumodd);}}
		ll ans=0LL;
		if(N==1) {cout<<1<<endl; continue;}
		if(N==2)
		{
			if(a[0]!=a[1]) {cout<<2<<endl; continue;} else {cout<<1<<endl; continue;}
		}
		//Case 1: P...PC...C
		ll minr=0LL; while(2LL*ps[minr]<=sum) {minr++;}
		ans+=(N-minr);
		ll minsumP;
		//Case 2.1: C...CPCPC...PCP...P
		ans+=solve(0,N-1,sum/2LL +1LL);
		//cout<<solve(0,N-1,sum/2LL +1LL)<<endl;
		//Case 2.2: PC..CPCPC...PCP...P, at least 2 C's in the block
		if(N>=3) {ans+=solve(3,N-1,sum/2LL +1LL-a[0]);}
		//Case 2.3: C..CPCPC...PCP...PC, at least 2 P's in the block
		if(N>=3) {ans+=solve(0,N-4,sum/2LL +1LL-a[N-2]-a[N-3]);}
		//Case 2.4: PC...CPCPC...PCP...PC, at least 2C's and 2 P's inm the block
		if(N>=6) {ans+=solve(3,N-4,sum/2LL +1LL-a[0]-a[N-2]-a[N-3]);}
		//Exclude cases PC..C and P..PC,P..P
		if(N>=3 && a[0]>=sum/2 +1LL) {ans--;} 
		if(N>=3 && sum-a[N-1]>=sum/2 +1LL) {ans--;}
		ans--;
		ans%=mod; if(ans<0) {ans+=mod;}
		cout<<ans<<endl;
	}
    return 0;
}