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 <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <bitset>
#include <cmath>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <queue>
using namespace std;
template<typename A,typename B>
string to_string(pair<A,B> p);

template<typename A,typename B,typename C>
string to_string(tuple<A,B,C> p);

template<typename A,typename B,typename C,typename D>
string to_string(tuple<A,B,C,D> p);

string to_string(const string &s)
{
    return '"'+s+'"';
}
string to_string(const char *s)
{
    return to_string((string)s);
}
string to_string(bool b)
{
    return (b?"true":"false");
}
string to_string(vector<bool> v)
{
    bool first=true;
    string res="{";
    for(int i=0;i<static_cast<int>(v.size());i++)
    {
        if(!first)
        {
            res+=", ";
        }
        first=false;
        res+=to_string(v[i]);
    }
    res+="}";
    return res;
}
template<size_t N>
string to_string(bitset<N> v)
{
    string res="";
    for(size_t i=0;i<N;i++)
    {
        res+=static_cast<char>('0'+v[i]);
    }
    return res;
}
template <typename A>
string to_string(A v)
{
    bool first=true;
    string res="{";
    for(const auto &x:v)
    {
        if(!first)
        {
            res+=", ";
        }
        first=false;
        res+=to_string(x);
    }
    res+="}";
    return res;
}
template<typename A,typename B>
string to_string(pair<A, B> p)
{
    return "("+to_string(p.first)+", "+to_string(p.second)+")";
}
template <typename A,typename B,typename C>
string to_string(tuple<A,B,C> p)
{
    return "("+to_string(get<0>(p))+", "+to_string(get<1>(p))+", "+to_string(get<2>(p))+")";
}
template<typename A,typename B,typename C,typename D>
string to_string(tuple<A,B,C,D> p)
{
    return "("+to_string(get<0>(p))+", "+to_string(get<1>(p))+","+to_string(get<2>(p))+", "+to_string(get<3>(p))+")";
}
void debug(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug(Head H,Tail...T)
{
    cerr<<" "<<to_string(H);
    debug(T...);
}
struct Fast_power
{
    long long integer(long long n,long long e,long long my_mod=9223372036854775807LL)
    {
        long long ans=1;
        while(e)
        {
            if(e&1) ans=(ans*n)%my_mod,e--;
            else n=(n*n)%my_mod,e>>=1;
        }
        return ans;
    }
    vector<vector<long long>> matrix_multiply(vector<vector<long long>> a,vector<vector<long long>> b)
    {
        vector<vector<long long>> c(a.size(),vector<long long>(b[0].size(),0));
        for(int i=0;i<a.size();i++)
            for(int q=0;q<b[0].size();q++)
            {
                long long num=0;
                for(int e=0;e<a[0].size();i++)
                    num+=a[i][e]*b[e][q];
                c[i][q]=num;
            }
        return c;
    }
    // long long matrix(vector<vector<long long>> &n,long long e,vector<long long> &s,long long my_mod=9223372036854775807LL)//矩阵快速幂
    // {
    //     vector<vector<long long>> ans(n.size(),vector<long long>(n.size(),1));
    //     while(e)
    //     {
    //         if(e&1) ans=matrix_multiply(ans,n),e--;
    //         else n=matrix_multiply(n,n),e>>=1;
    //     }
    // }
};
struct Euclidean//欧几里得 
{
    int gcdi(int a,int b)
    {
        return b?gcdi(b,a%b):a;
    }
    double gcdf(double a,double b,double accuracy)//浮点数的最大公约数
    {
        return b<=accuracy?a:gcdf(b,fmod(a,b),accuracy);
    }
    //扩展欧几里得

    //类欧几里得
};

#define DijkstraDist int 
const int maxnD=250000+5;
const DijkstraDist INFD=0x3f3f3f3f;
struct Dijkstra
{
    struct Edge
    {
        int from,to;
        DijkstraDist dist;
    };
    struct HeapNode
    {
        DijkstraDist d;
        int u;
        bool operator < (const HeapNode&rhs) const
        {
            return d>rhs.d;
        }
    };
    vector<Edge> edges;
    vector<int> G[maxnD];
    bool done[maxnD];
    DijkstraDist d[maxnD];
    int p[maxnD],n;
    void init(int n)
    {
        this->n=n;
        for(int i=0;i<=n;i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,DijkstraDist dist)
    {
        edges.push_back((Edge){from,to,dist});
        int m=edges.size();
        G[from].push_back(m-1);
    }
    void dijkstra(int s)
    {
        priority_queue<HeapNode> q;
        memset(d,INFD,sizeof(d));
        d[s]=0;
        memset(done,0,sizeof(done));
        q.push((HeapNode){0,s});
        while(!q.empty())
        {
            HeapNode x=q.top();
            q.pop();
            int u=x.u;
            if(done[u]) continue;
            done[u]=true;
            for(int i=0;i<G[u].size();i++)
            {
                Edge& e=edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist)
                {
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
    }
};

const int maxnL=500000+5;
const int INFL=0x3f3f3f3f;
struct LIS
{
    int g[maxnL],a[maxnL],d[maxnL];
    void lis(int n)
    {
        for(int i=1;i<=n;i++) g[i]=INFL;
        for(int i=1;i<n;i++)
        {
            int k=lower_bound(g+1,g+n+1,a[i])-g;
            g[k]=a[i];
        }
    }
};
const int maxnS=200000+5;
struct SegmentTree
{
    int a[maxnS];
    int sumv[maxnS*4],minv[maxnS*4],maxv[maxnS*4],addv[maxnS*4],setv[maxnS*4];
    int lc,rc,v;
    int _min,_max,_sum;
    void build(int l,int r,int o)
    {
        if(l==r) return void(sumv[o]=minv[o]=maxv[o]=a[l]);
        build(l,(l+r)>>1,o<<1);
        build(((l+r)>>1)+1,r,o<<1|1);
    }
    void maintain(int l,int r,int o)
    {
        sumv[o]=minv[o]=maxv[o]=a[l];
        if(r>l)
        {
            sumv[o]=sumv[o<<1]+sumv[o<<1|1];
            minv[o]=min(minv[o<<1],minv[o<<1|1]);
            maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
        }
        minv[o]+=addv[o],maxv[o]+=addv[o],sumv[o]+=addv[o]*(r-l+1);
    }
    void update(int l,int r,int o)
    {
        if(l>=lc&&r<=rc) addv[o]+=v;
        else
        {
            int m=(l+r)>>1;
            if(lc<=m) update(l,(l+r)>>1,o<<1);
            if(rc>m) update(((l+r)>>1)+1,r,o<<1|1);
        }
        maintain(l,r,o);
    }
    void query(int l,int r,int o,int add)
    {
        if(lc<=l&&r<=rc) 
        {
            _sum+=sumv[o]+add*(r-l+1);
            _min=min(_min,minv[o]+add);
            _max=max(_max,maxv[o]+add);
        }
        else
        {
            int m=(l+r)>>1;
            if(lc<=m) query(l,m,o<<1,add+addv[o]);
            if(rc>m) query(m+1,r,o<<1|1,add+addv[o]);
        }
    }
};

const int maxnB=400000+5;
struct BIT
{
    int c[maxnB],n; 
    int lowbit(int x)
    {
        return x&-x;
    }
    int sum(int x)
    {
        int ret=0;
        while(x>0)
        {
            ret+=c[x];
            x-=lowbit(x);
        }
        return ret;
    }
    void add(int x,int d)
    {
        while(x<=n)
        {
            c[x]+=d;
            x+=lowbit(x);
        }
    }
};

const int maxnEC=200000+5;
struct EXCRT//扩展中国剩余定理
{
    //x%b[i]=a[i];
    long long ai[maxnEC],bi[maxnEC],n;
    inline long long exgcd(long long a,long long b,long long &x,long long &y)
    {
        if(!b)
        {
            x=1,y=0;
            return a;
        }
        long long gcd=exgcd(b,a%b,x,y);
        long long t=x;
        x=y,y=t-(a/b)*y;//递归解方程。 
        return gcd;
    }
    inline long long mul(long long a,long long b,long long mod) //必须自己打乘法不然会爆long long 
    {
        long long s=0;
        while(b) 
        {
            if(b&1) s=(s+a)%mod;
            a=(a+a)%mod;
            b>>=1;
        }
        return s%mod;
    }
    long long excrt()
    {
        long long x=0,y=0,k;
        long long M=bi[1],ans=ai[1];//第一个方程的解特判
        for(int i=2;i<=2;i++)
        {
            long long a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;//ax≡c(mod b)
            long long gcd=exgcd(a,b,x,y),bg=b/gcd;
            if(c%gcd!=0) return -1; //是否无解
            x=mul(x,c/gcd,bg);
            ans+=x*M;//更新前k个方程组的答案
            M*=bg;//M为前k个m的lcm
            ans=(ans%M+M)%M;
        }
        return (ans%M+M)%M;
    }
};

#define PI acos(-1);
#define fri freopen("in.txt", "r", stdin)
#define fro freopen("out.txt", "w", stdout)
#define pb push_back
#define all(a) a.begin(),a.end()
#define si(a) a.size()
#define in insert
#define fora(i,l,r) for(int i=l;i<r;i++)
#define forb(i,l,r) for(int i=l;i<=r;i++)
#define forc(i,l,r) for(int i=l;i>r;i--)
#define ford(i,l,r) for(int i=l;i>=r;i--)
#define fi first
#define ed second
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=200000+5;
ll sum1[maxn],a[maxn],sum2[maxn],sum3[maxn];
const ll mod=998244353;
int bin(int llimit,int rlimit,ll pre)
{
    int pos=0;
    int l=llimit,r=rlimit;
    // debug(llimit,rlimit,pre);
    while(l<=r)
    {
        int m=(l+r)>>1;
        ll d;
        if(llimit&1) d=sum2[m]-sum2[llimit-1];
        else d=sum3[m]-sum3[llimit-1];
        if(pre-d*2>0) pos=max(pos,m),l=m+1;
        else r=m-1;
    }
    // cerr<<pos<<" "<<llimit<<endl;
    if(!pos) return 0;
    return (pos-llimit)/2+1;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin>>tt;
    while(tt--)
    {
        int n;
        cin>>n;
        forb(i,1,n) cin>>a[i],sum1[i]=sum1[i-1]+a[i];
        for(int i=1;i<=n;i++)
        {
            if(i&1) sum2[i]=sum2[max(0,i-2)]+a[i],sum3[i]=sum3[i-1];
            else sum3[i]=sum3[i-2]+a[i],sum2[i]=sum2[i-1];
        }
        ll ans=0;
        for(int i=1;i<=n;i++)//p....
        {
            if(i!=1&&sum1[n]-sum1[i]<sum1[i]) ans++;
        }
        // cerr<<ans<<endl;
        for(int i=1;i<=n;i++)//c......
        {
            // c....c
            if(i<=n-3)
            ans=(ans+bin(i,n-3,-(a[n]+sum1[i-1])+sum1[n-1]-sum1[i-1]))%mod;
            // c.....
            ans=(ans+bin(i,n,-sum1[i-1]+sum1[n]-sum1[i-1]))%mod;
        }
        for(int i=2;i<=n;i++)//pc.....
        {
            // pc....c
            if(i<=n-3)
                ans=(ans+bin(i,n-3,a[1]-a[n]+sum1[n-1]-sum1[i-1]-(sum1[i-1]-sum1[1])))%mod;
            // pc....
            ans=(ans+bin(i,n,sum1[n]-sum1[i-1]+a[1]-(sum1[i-1]-sum1[1])))%mod;
        }
        if(n==1) ans++;
        cout<<ans<<endl;
    }
	return 0;
}
/*
3
5
2 1 2 1 1
*/