#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
long long int a[n],neg,pos;
neg=pos=0;
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
if(i!=0)
{
if(a[i]<0)
neg+=(-a[i]);
else
pos+=a[i];
}
}
long long int w,sum=a[0];
w=1;
for(int i=1;i<n;i++)
{
if(a[i]>=0)
{
w++;
sum+=(a[i]*w);
pos-=a[i];
}
else
{
if(pos<neg)
{
w=2;
sum+=(a[i]*w);
neg+=a[i];
}
else
{
w++;
sum+=(a[i]*w);
neg+=a[i];
}
}
}
printf("%lld\n",sum);
}
}