#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <chrono>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define Endl "\n"

// Macros
#define int long long
// #define ll long long
#define ld long double
#define vt vector
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pair<int,int>>

#define pii pair<int,int>

constexpr ll inf = 9e18;


#define pb push_back
#define em emplace_back
#define all(X) (X).begin(), (X).end()
#define allr(X) (X).rbegin(), (X).rend()
#define sz(X) (int)X.size()

#define each(x, a) for (auto &x: a)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define forr(i, n) for (int i = n; i >=0; --i)
#define rep(i,a,b) for(int i = a; i <= b; i++)

// Debug macro
string to_string(string s){return '"'+s+'"';}
string to_string(const char* s){return to_string((string)s);}
string to_string(const bool& b){return(b?"true":"false");}
template<class T>string to_string(T x){ostringstream sout;sout<<x;return sout.str();}
template<class A,class B>string to_string(pair<A,B> p){return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template<class A>string to_string(const vector<A> v){
    int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
    return res;
}
template<class A>string to_string(const set<A> v){
    int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
    return res;
}
template<class A, class B>string to_string(const map<A, B> v){
    int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
    return res;
}
template<class A>string to_string(const multiset<A> v){
    int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
    return res;
}
void debug_out(){puts("");}
template<class T,class... U>void debug_out(const T& h,const U&... t){cerr<<" "<<to_string(h);debug_out(t...);}
#ifndef ONLINE_JUDGE
#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__),cerr<<"\n";
#else
#define dbg(...) 233;
#endif

// Read
template<typename T1, typename T2> // cin >> pair<T1, T2>
istream& operator>>(istream &istream, pair<T1,T2> &p){ return (istream >> p.first >> p.second); }
template<typename T> // cin >> vector<T>
istream& operator>>(istream &istream, vector<T> &v){
  for(auto &it: v) cin >> it;
  return istream;
}
// Print
template<typename T1, typename T2> // cout << pair<T1, T2>
ostream& operator<<(ostream &ostream, const pair<T1, T2> &p){ return (ostream << p.first << " " << p.second); }
template<typename T> //cout << vector<T>
ostream& operator<<(ostream &ostream, const vector<T> &c){ for (auto &it: c) cout << it << " "; return ostream;}

// Utility functions
template<typename T>
void print(T &&t) {cout << t << Endl;}
template <typename T, typename... Args>
void print(T &&t, Args &&... args){
  cout << t << " ";
  print(forward<Args>(args)...);
}

int n = -inf, m = -inf;
void solve(){
  int k,i, j, q, x, y;
  k = i = j = q = x = y = n = m = -1;
  cin >> n;
  vi a(n+1);
  rep(i,1,n) cin >> a[i];
  vi pre(n+1);
  rep(i,1,n) pre[i] = pre[i-1]+a[i];
  vi pre2(n+1);
  rep(i,1,n) pre2[i] = pre2[i-1]+pre[i];
  dbg(pre);
  dbg(pre2);
  int ans = 0;
  auto calc = [&] (int i, int j){
    return pre2[j]-(pre2[i-1]+pre[i-1]*(j-i+1));
  };
  vi nsl(n+2);
  stack<int> st;
  // a.pb(-inf); // NOTICE
  pre.pb(-inf);
  st.push(n+1);
  for(i = n; i >= 0; i--){
    while(pre[st.top()] >= pre[i]){
      st.pop();
    }
    nsl[i] = st.top();
    st.push(i);
  }
  // int temp = calc(1,3);
  // dbg(temp);
  // dbg()
  rep(i,1,n){
    if(a[i] < 0) continue;
    int till = nsl[i-1]-1;
    ans += calc(i,till);
    dbg(i,till);
    // dbg(i,ans);
  }
  print(ans);
}


signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  auto start = std::chrono::system_clock::now();
#endif

  int t = 1;
  cin >> t;
  rep(tt, 1,t){
    // dbg(t);
    cout << "Case #" << tt << ": ";
    solve();
#ifdef LOCAL
    auto end = std::chrono::system_clock::now();
    std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "ms" << Endl;
#endif
  }
#ifdef LOCAL
  auto end = std::chrono::system_clock::now();
  std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "ms" << Endl;
  cerr << "Completed" << Endl;
#endif
}

/* stuff you should look for
  * constraints
    * int overflow, array bounds
    * special cases (n=1, n = 0?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/