#include<cstdio>
#include<algorithm>

#define	rep(i,n)	for(int i=0;i<(n);i++)

using namespace std;

int main(){
	int T;	scanf("%d",&T);
	while(T--){
		int n,Ea[80];	scanf("%d",&n);
		rep(i,n)	scanf("%d",Ea+i);

		int dp[80][161]={};	dp[0][0]=Ea[0];
		for(int i=1;i<n;i++)rep(s,161){
			int b=dp[i-1][s];
			dp[i][b]=max(dp[i][b],Ea[i]);
			if(b>0){
				dp[i][b-1]=max(dp[i][b-1],Ea[i]+s);
			}
		}

		printf("%d\n",*max_element(dp[n-1],dp[n-1]+161));
	}

	return 0;
}