#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
long long A[MAXN],pref[MAXN*2][2],pf[MAXN*2],mnpref[MAXN],mnsuff[MAXN],L[MAXN];
deque<long long> dq;
bool f(int i,int j,int n)
{
    if(dq.empty()||dq.back()!=j-1)
    {
        while(!dq.empty()&&pf[dq.back()]>=pf[j-1]) dq.pop_back();
        dq.push_back(j-1);
    }
    long long a=pref[j-1][0]-pref[i-1][0],fa=a-(pf[dq.front()]-pf[i-1]-pref[j-1][1]+pref[i-1][1]);
    long long b=pref[j-1][1]-pref[i+n-1][1],fb=-(min(mnpref[i-1],mnsuff[j-1])-pf[j-1]);
    return max(fa,fb)<=min(a,b);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>A[i];
        for(int i=1;i<=n*2;i++)
        {
            pf[i]=pf[i-1]+A[(i-1)%n+1];
            pref[i][0]=pref[i-1][0],pref[i][1]=pref[i-1][1];
            if(A[(i-1)%n+1]>0) pref[i][0]+=A[(i-1)%n+1];
            else pref[i][1]+=A[(i-1)%n+1];
        }
        for(int i=1;i<=n;i++) mnpref[i]=min(mnpref[i-1],pf[i]);
        mnsuff[n+1]=0;
        for(int i=n;i+1;i--) mnsuff[i]=min(mnsuff[i+1],pf[i]);
        long long ans=0,l=1,r=1;
        dq.push_back(0);
        for(int i=1;i<=n;i++)
        {
            while(l<=n&&!f(i,l,n)) l++;
            if(dq.front()==i-1) dq.pop_front();
            ans-=l,L[i]=l;
        }
        while(!dq.empty()) dq.pop_back();
        dq.push_back(0);
        for(int i=1;i<=n;i++)
        {
            while(r<L[i]) f(i,r++,n);
            while(r<=n&&f(i,r,n)) r++;
            if(dq.front()==i-1) dq.pop_front();
            ans+=r;
        }
        cout<<ans<<'\n';
        while(!dq.empty()) dq.pop_back();
    }
}