#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn = ;

const int INF = 0x3f3f3f3f;

int dp1[maxn];

int dp2[maxn];

int a[maxn];

int N;

int main()

{

    int T;

    cin>>T;

    while(T--){

        scanf("%d",&N);

        for(int i=;i<=N;i++) scanf("%d",&a[i]);

        dp1[] = -INF;

        for(int i=;i<=N;i++){

            dp1[i] = max(dp1[i-],) + a[i];

        }

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

            dp1[i] = max(dp1[i],dp1[i-]);

        dp2[N+] = -INF;

        for(int i=N;i>=;i--){

            dp2[i] = max(dp2[i+],) + a[i];

        }

        for(int i=N-;i>=;i--){

            dp2[i] = max(dp2[i],dp2[i+]);

        }

        int ans = -INF;

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

            ans = max(ans,dp1[i]+dp2[i+]);

        printf("%d\n",ans);

    }

}