#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
void update(int& x, int y) { if(x < y) x = y; }

int main(){
  int T;
  cin >> T;
  while(T --){
    int L; cin >> L;
    vector<int> A(L);
    REP(i, L) cin >> A[i];
    int dp[100][400] = {}; // 0からiまでのEa鎖で、i - 1が+kのとき、iが取れる増加値の最大
    REP(i, L)REP(j, 400) dp[i][j] = -INF;
    dp[0][0] = A[0]; // L = 1の例外
    dp[1][A[0]] = A[1]; //初期値
    // (現在のEa鎖のindex, 一つ前の基の値, 現在の基の値) = (i, j, k)
    // (i, j, k) -> (i + 1, k, A[i + 1]) (伝播しない)
    //           -> (i + 1, k - 1, j + A[i + 1]) (伝播した)
    for(int i = 1; i + 1 < L; i++){
      for(int j = 0; j <= 4 * i; j++){
        if(dp[i][j] >= 0) update(dp[i + 1][dp[i][j]], A[i + 1]);
        if(dp[i][j] >= 1) update(dp[i + 1][dp[i][j] - 1], j + A[i + 1]);
      }
    }
    int ans = 0;
    for(int i = 0; i < 4 * L; i++) update(ans, dp[L - 1][i]);
    cout << ans << endl;
  }
  return 0;
}