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.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define PI 3.14159265
#define fast ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
typedef pair<ll,ll> pli;
typedef pair<int,int> pii;
typedef pair<ld,ld> pld;
ll MOD=998244353;
ll MX=1000000000000000;

ll T;
ll n;
ll a[200200];
ll sum1[200200];
ll sum2[200200];
bool check1(ll i,ll ind)
{
    ll x=i;
    ll y=i+2*ind-1;
    if(sum1[n]-sum1[y-1]-sum1[x]+sum2[x+1]-sum2[y]>0)
        return 1;
    return 0;
}
bool check2(ll i,ll ind)
{
    ll x=i;
    ll y=i+2*ind-1;
    if(2*a[1]+sum1[n]-sum1[y-1]-sum1[x]+sum2[x+1]-sum2[y]>0)
        return 1;
    return 0;
}
bool check3(ll i,ll ind)
{
    ll x=i;
    ll y=i+2*ind-1;
    if(-2*a[n]+sum1[n]-sum1[y-1]-sum1[x]+sum2[x+1]-sum2[y]>0)
        return 1;
    return 0;
}
bool check4(ll i,ll ind)
{
    ll x=i;
    ll y=i+2*ind-1;
    if(-2*a[n]+2*a[1]+sum1[n]-sum1[y-1]-sum1[x]+sum2[x+1]-sum2[y]>0)
        return 1;
    return 0;
}
int main()
{
    fast;
    //freopen("input.txt","r",stdin);
    cin>>T;
    while(T--)
    {
        cin>>n;
        ll sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum+=a[i];
            sum1[i]=sum;
        }
        sum2[n+1]=0;
        for(int i=n;i>=1;i--)
        {
            sum2[i]=a[i]-sum2[i+1];
        }
        ll it=n+1;
        ll res=0;
        ll psum=0;
        ll csum=0;
        for(int i=1;i<=n;i++)
        {
            psum+=a[i];
            if(psum>sum-psum)
                res++;
        }
        psum=0;
        //cout<<"res="<<res<<endl;
        //1
        //cout<<"Now in 1:\n";
        for(int i=1;i<=n-1;i++)
        {
            ll lo=1;
            ll hi=n;
            ll ans=0;
            //cout<<"i="<<i<<endl;
            while(lo<=hi)
            {
                ll mid=(lo+hi)/2;
                //cout<<mid<<" "<<check1(i,mid)<<endl;
                if(2*mid-1+i>n||!check1(i,mid))
                {
                    hi=mid-1;
                }
                else
                {
                    ans=max(ans,mid);
                    lo=mid+1;
                }
            }
            res+=ans;
        }
        //cout<<"After 1 res="<<res<<endl;
        //2
        //cout<<"Now in 2:\n";
        for(int i=2;i<=n-1;i++)
        {
            ll lo=1;
            ll hi=n;
            ll ans=0;
            //cout<<"i="<<i<<endl;
            while(lo<=hi)
            {
                ll mid=(lo+hi)/2;
                //cout<<mid<<" "<<check2(i,mid)<<endl;
                if(2*mid-1+i>n||!check2(i,mid))
                {
                    hi=mid-1;
                }
                else
                {
                    ans=max(ans,mid);
                    lo=mid+1;
                }
            }
            res+=ans;
        }
        //cout<<"After 2 res="<<res<<endl;
        //3
        //cout<<"Now in 3:\n";
        for(int i=1;i<=n-2;i++)
        {
            //cout<<"i="<<i<<endl;
            ll lo=1;
            ll hi=n;
            ll ans=0;
            while(lo<=hi)
            {
                ll mid=(lo+hi)/2;
                //cout<<mid<<" "<<check3(i,mid)<<endl;
                if(2*mid-1+i>=n||!check3(i,mid))
                {
                    hi=mid-1;
                }
                else
                {
                    ans=max(ans,mid);
                    lo=mid+1;
                }
            }
            res+=ans;
        }
        //cout<<"After 3 res="<<res<<endl;
        //4
        //cout<<"Now in 4:\n";
        for(int i=2;i<=n-2;i++)
        {
            ll lo=1;
            ll hi=n;
            ll ans=0;
            //cout<<"i="<<i<<endl;
            while(lo<=hi)
            {
                ll mid=(lo+hi)/2;
                //cout<<mid<<" "<<check4(i,mid)<<endl;
                if(2*mid-1+i>=n||!check4(i,mid))
                {
                    hi=mid-1;
                }
                else
                {
                    ans=max(ans,mid);
                    lo=mid+1;
                }
            }
            res+=ans;
        }
        //cout<<"After 4 res="<<res<<endl;
        res%=MOD;
        cout<<res<<endl;
    }

    return 0;
}
