#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

int n;

ll a[];

ll work()

{

    ll temp=,m=;

    for(int i=;i<n;i++)

    {

        temp+=a[i];

        if(temp<) temp=;

        if(m<temp) m=temp;

    }

    return m;

}

int main()

{

    int t;

    ll sum,sum1,sum2;

    scanf("%d",&t);

    while(t--)

    {

        sum=;

        scanf("%d",&n);

        for(int i=;i<n;i++)

        {

            scanf("%lld",&a[i]);

            sum+=a[i];

        }

        sum1=work();

        for(int i=;i<n;i++)

            a[i]=-a[i];

        sum2=work();

       // printf("%lld %lld %lld\n",sum,sum1,sum2);

        sum=max(sum+sum2,sum1);

        printf("%lld\n",sum);

    }

    return ;

}