#!/usr/bin/ruby

M = 40

gets.to_i.times do |_|
  n = gets.to_i
  e = gets.chomp.split(" ").map {|x| x.to_i}

  dp = Array.new n
  n.times {|i| dp[i] = Array.new M,0 }

  dp[0][0] = e[0]
  for i in 1...n
    dp[i][e[i-1]] = e[i]
  end

  for i in 2...n
    for b in 0...M
      c = dp[i-1][b]
      dp[i][c] = [dp[i][c], e[i]].max
      if c > 0
        dp[i][c-1] = [ dp[i][c-1], b + e[i] ].max
      end
    end
  end

  puts dp[n-1].max

end